The problem
Sort a linked list using insertion sort and return the sorted head.
Stuck? Reveal hints one at a time
How to approach it
- 1Create a dummy node for the sorted result.
- 2For each node in the input: detach it, walk from the dummy while next value < node value.
- 3Splice the node in at that point.
- 4Return dummy.next.
Key insight
On lists, insertion sort moves POINTERS instead of shifting elements — the O(n) shift cost of arrays disappears, though the O(n) search per element remains.
The solution
Watch out for
- Save current.next BEFORE splicing — the splice destroys it.
- An optimization: keep a tail pointer and only restart the scan when the new value is smaller than the tail.