✔️ [Python3] INSERTION SORT, Explained
The idea is to create a dummy node that would be the head of the sorted part of the list. Iterate over the given list and one by one add nodes to the sorted lis
The idea is to create a dummy node that would be the head of the sorted part of the list. Iterate over the given list and one by one add nodes to the sorted list at the appropriate place following the insertion sort algorithm.\n\nTime: **O(n^2)**\nSpace: **O(1)**\n\nRuntime: 1677 ms, faster than **51.65%** of Python3 online submissions for Insertion Sort List.\nMemory Usage: 16.4 MB, less than **29.01%** of Python3 online submissions for Insertion Sort List.\n\n```\nclass Solution:\n    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n        sort = ListNode() #dummy node\n\n        cur = head\n        while cur:\n            sortCur = sort\n            while sortCur.next and cur.val >= sortCur.next.val:\n                sortCur = sortCur.next\n                \n            tmp, sortCur.next = sortCur.next, cur\n            cur = cur.next\n            sortCur.next.next = tmp\n            \n        return sort.next\n```
['Python3']