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
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