[Python] Insertion Sort, explained
In this problem we are asked to implement insertion sort on singly-linked list data structure. And we do not really have a choice how to do it: we just need to 
In this problem we are asked to implement insertion sort on singly-linked list data structure. And we do not really have a choice how to do it: we just need to apply definition of Insertion Sort. Imagine, that we already sorted some part of data, and we have something like:\n`1 2 3 7` **4** `6`,\nwhere by bold **4** I denoted element we need to insert on current step. How we can do it? We need to iterate over our list and find the place, where it should be inserted. Classical way to do it is to use **two pointers**: `prv` and `nxt`, stands for previous and next and stop, when value of `nxt` is greater than value of node we want ot insert. Then we insert this element into correct place, doing `curr.next = next, prv.next = curr`. Also, now we need to update our `curr` element: for that reason in the beginning of the loop we defined `curr_next = curr.next`, so we can update it now.\n\n**Complexity**: time complexity is `O(n^2)`, as Insertion sort should be: we take `O(n)` loops with `O(n)` loop inside. Space complexity is `O(1)`, because what we do is only change connections between our nodes, and do not create new data.\n\n```\nclass Solution:\n    def insertionSortList(self, head):\n        dummy = ListNode(-1)\n        curr = head\n        while curr:\n            curr_next = curr.next\n            prv, nxt = dummy, dummy.next\n            while nxt:\n                if nxt.val > curr.val: break\n                prv = nxt\n                nxt = nxt.next\n                \n            curr.next = nxt\n            prv.next = curr\n            curr = curr_next\n        \n        return dummy.next\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]