Python 3 (Modifying Node Pointers)


#1
def insertionSortList(self, A):
    if A==None or A.next==None:
        return A
    next_ele = A.next
    head = A
    prev2 = A
    dummy = ListNode(0)
    dummy.next = A
    while next_ele:
        curr = dummy.next
        prev1 = dummy
        while curr and curr!=next_ele:
            if curr.val>next_ele.val:
                temp = next_ele.next
                prev2.next = next_ele.next
                next_ele.next = curr
                prev1.next = next_ele
                next_ele = temp
                break
            prev1 = curr
            curr = curr.next
        if curr==next_ele:
            prev2 = next_ele
            next_ele = next_ele.next
    return dummy.next