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

• 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?)
if head.val <= second.val:
else:
tmp = pre = second
while second and second.val < head.val:
pre = second
second = second.next
return tmp

# Iteratively
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)