https://leetcode.com/problems/insertion-sort-list

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: 1 2 3 7 4 6, where 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.

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.

class Solution:
    def insertionSortList(self, head):
        dummy = ListNode(-1)
        curr = head
        while curr:
            curr_next = curr.next
            prv, nxt = dummy, dummy.next
            while nxt:
                if nxt.val > curr.val: break
                prv = nxt
                nxt = nxt.next
                
            curr.next = nxt
            prv.next = curr
            curr = curr_next
        
        return dummy.next

If you like the solution, you can upvote it on leetcode discussion section: Problem 0147