The problem
Sort a linked list in O(n log n) time. The follow-up asks for O(1) memory (excluding recursion).
Stuck? Reveal hints one at a time
How to approach it
- 1Base case: empty or single node.
- 2Fast/slow pointers find the midpoint; sever the list into two halves (set mid-previous.next = null).
- 3Recursively sort both halves.
- 4Merge the sorted halves with a dummy head, relinking nodes.
Key insight
Merge sort is THE list sort: splitting is pointer surgery, merging needs no random access, and stability is automatic — everything arrays make painful is natural here.
The solution
Watch out for
- Forgetting to CUT the list (prev.next = null) makes the recursion never shrink.
- The true-O(1)-space answer is bottom-up merge sort with doubling run lengths — mention it for the follow-up.