Insert In Sorted Linked List

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def insert(self, head, value): """ input: ListNode head, int value return: ListNode """ # write your solution here new_node = ListNode(value) # empty list if (head == None): head = new_node return head # one element list elif (head.next == None): if (head.val >= value): # insert before head new_node.next = head head = new_node return head else: # insert after head head.next = new_node return head # at least two elements in list else: prev = head curr = head while(curr != None): if (curr.val < value): prev = curr curr = curr.next else: break # now curr.val > value and prev.val <= value. Insert the node between prev and curr prev.next = new_node new_node.next = curr return head