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 b
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.\n        \n    # Recursively, TLE (Why?)\n    def insertionSortList1(self, head):\n        if not head or not head.next:\n            return head\n        second = self.insertionSortList(head.next)\n        if head.val <= second.val:\n            head.next = second\n            return head\n        else:\n            tmp = pre = second\n            while second and second.val < head.val:\n                pre = second\n                second = second.next\n            head.next = second\n            pre.next = head\n            return tmp\n    \n    # Iteratively         \n    def insertionSortList(self, head):\n        if not head or not head.next:\n            return head\n        dummy = ListNode(0)\n        dummy.next = node = head\n        while node.next:\n            if node.val <= node.next.val:\n                node = node.next\n            else:\n                pre = dummy\n                while pre.next.val < node.next.val:\n                    pre = pre.next\n                tmp = node.next\n                node.next = tmp.next\n                tmp.next = pre.next\n                pre.next = tmp\n        return dummy.next
['Recursion', 'Iterator', 'Python']