Concise python solution with comments


  • 8
    Z
    def insertionSortList(self, head):
        cur = dummy = ListNode(0)
        while head:
            if cur and cur.val > head.val: # reset pointer only when new number is smaller than pointer value
                cur = dummy
            while cur.next and cur.next.val < head.val: # classic insertion sort to find position
                cur = cur.next
            cur.next, cur.next.next, head = head, cur.next, head.next # insert
        return dummy.next

  • 0
    K

    the following optimization is awesome!

    if cur and cur.val > head.val: # reset pointer only when new number is smaller than pointer value
                cur = dummy
    

  • 0

    Hi @zhuyinghua1203 , this solution is great!

    I think we can improve it a little bit by removing the check of 'cur' here since cur is always a ListNode:

     if cur and cur.val > head.val: # reset pointer only when new number is smaller than pointer value
    

    We can just use this:

     if cur.val > head.val: # reset pointer only when new number is smaller than pointer value
    

Log in to reply
 

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