Leetcode 147: Insertion Sort List

https://leetcode.com/problems/insertion-sort-list/

Sort a linked list using insertion sort.

 

Code 

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        new_head = ListNode(0)
        cur = head
        while cur:
            isrt = new_head
            next = cur.next
            
            while isrt.next and isrt.next.val < cur.val:
                isrt = isrt.next
            
            cur.next = isrt.next
            isrt.next = cur
            cur = next
            
        return new_head
            

 

Idea

By definition, insertion sort is inserting each element to the current sorted array by comparing it to the elements in the current sorted array. It requires O(N^2) time asymptotically. In my code, `isrt` is used to locate the correct position to insert the new element. It is set to the head every time a new element needs to be inserted (Line 16).  

However, the code above can’t pass the leetcode OJ. One way to circumvent it is to set `isrt` more passively (set `isrt` only when very necessary) instead of setting it to head for every new element to be inserted.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        new_head = ListNode(0)
        cur = head
        isrt = new_head
        
        while cur:
            next = cur.next
            
            if not isrt or not isrt.next or isrt.next.val>=cur.val:
                isrt = new_head
            
            while isrt.next and isrt.next.val < cur.val:
                isrt = isrt.next
            
            cur.next = isrt.next
            isrt.next = cur
            cur = next
            
            
        return new_head.next