Python accepted iterative solution (Another solution is about 330ms).


  • -1
    C

    suppose already sorted the part from the second node, then just need to merge the first node with the second part, if head.val is smaller, then the second can be connected behind head node, if head.val is larger than the value of the returned node, then we need to find the position to insert head, and return the returned node. The iterative method is quite easy to follow, when we find the node's value is smaller than that of the previous node, we need to find an insertion position for that node in positions ahead.

    # Recursively, TLE (Why?)
    def insertionSortList1(self, head):
        if not head or not head.next:
            return head
        second = self.insertionSortList(head.next)
        if head.val <= second.val:
            head.next = second
            return head
        else:
            tmp = pre = second
            while second and second.val < head.val:
                pre = second
                second = second.next
            head.next = second
            pre.next = head
            return tmp
    
    # Iteratively         
    def insertionSortList(self, head):
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        dummy.next = node = head
        while node.next:
            if node.val <= node.next.val:
                node = node.next
            else:
                pre = dummy
                while pre.next.val < node.next.val:
                    pre = pre.next
                tmp = node.next
                node.next = tmp.next
                tmp.next = pre.next
                pre.next = tmp
        return dummy.next

  • 0
    C

    Here is an another iterative version (about 330ms):

    def insertionSortList(self, head):
        dummy = ListNode(0)
        dummy.next = head
        while head and head.next:
            while head and head.next and head.val <= head.next.val:
                head = head.next
            node = head.next
            if not node:
                break
            head.next = node.next  # delete "node"
            pre = dummy 
            while node.val > pre.next.val:
                pre = pre.next 
            node.next = pre.next  # insert "node" in the right position
            pre.next = node
        return dummy.next

Log in to reply
 

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