[Python3] 188ms Solution (explanation with visualization)
Idea\n- Add dummy_head before head will help us to handle the insertion easily\n- Use two pointers\n\t- last_sorted: last node of the sorted part, whose value i
**Idea**\n- Add `dummy_head` before `head` will help us to handle the insertion easily\n- Use two pointers\n\t- `last_sorted`: last node of the sorted part, whose value is the largest of the sorted part\n\t- `cur`: next node of `last_sorted`, which is the current node to be considered\n\n\tAt the beginning, `last_sorted` is `head` and `cur` is `head.next`\n- When consider the `cur` node, there\'re 2 different cases\n\t- `last_sorted.val <= cur.val`: `cur` is in the correct order and can be directly move into the sorted part. In this case, we just move `last_sorted` one step forward\n\t![image](https://assets.leetcode.com/users/images/996a6192-d1c4-4f0b-8fd5-a0c9f6b147cb_1619384454.3517435.png)\n\n\t- `last_sorted.val > cur.val`: `cur` needs to be inserted somewhere in the sorted part. In this case, we let `prev` start from `dummy_head` and iteratively compare `prev.next.val` and `cur.val`. If `prev.next.val > cur.val`, we insert `cur` between `prev` and `prev.next`\n\t- ![image](https://assets.leetcode.com/users/images/47c2462c-08d7-4eb2-8789-7aba83a84b91_1619384469.52542.png)\n\n\n**Implementation**\n```python\nclass Solution:\n    def insertionSortList(self, head: ListNode) -> ListNode:\n        \n        # No need to sort for empty list or list of size 1\n        if not head or not head.next:\n            return head\n        \n        # Use dummy_head will help us to handle insertion before head easily\n        dummy_head = ListNode(val=-5000, next=head)\n        last_sorted = head # last node of the sorted part\n        cur = head.next # cur is always the next node of last_sorted\n        while cur:\n            if cur.val >= last_sorted.val:\n                last_sorted = last_sorted.next\n            else:\n                # Search for the position to insert\n                prev = dummy_head\n                while prev.next.val <= cur.val:\n                    prev = prev.next\n                    \n                # Insert\n                last_sorted.next = cur.next\n                cur.next = prev.next\n                prev.next = cur\n                \n            cur = last_sorted.next\n            \n        return dummy_head.next\n```\n\n**Complexity**\n- Time: O(n^2)\n- Space: O(1)
['Iterator', 'Python', 'Python3']