Python AC solution without tricks


  • 1

    Code is not elegant but works. No need to introduce any tricks if you really understand the pseudo-code of insertion sort.

    for i ← 1 to length(A)-1
        j ← i
        while j > 0 and A[j-1] > A[j]
            swap A[j] and A[j-1]
            j ← j - 1
        end while
    end for
    

    It does comparison from the end of the sorted part that avoids useless comparison if the current element is in correct position. Thus, when we do it in linked-list, we also need to do this check although it is O(n) to find insertion position.

    Below is my code.

    class Solution(object):
        def insertionSortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if head is None:
                return head
            dummy = ListNode(-1)    # for inserting to the beginning of the list
            dummy.next = head
            p = head.next
            pre = head
            while p:
                next = p.next
                q = dummy
                if p.val < pre.val: # avoid unnecessary re-scan
                    while q.next != p and q.next.val <= p.val:
                        q = q.next
                    if q.next != p:
                        pre.next = p.next
                        tmp = q.next
                        q.next = p
                        p.next = tmp
                else:
                    pre = p # pre pointer update only when no insertion
                p = next
            return dummy.next
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.