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
   = head
            p =
            pre = head
            while p:
                next =
                q = dummy
                if p.val < pre.val: # avoid unnecessary re-scan
                    while != p and <= p.val:
                        q =
                    if != p:
                        tmp =
               = p
               = tmp
                    pre = p # pre pointer update only when no insertion
                p = next

Log in to reply

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