Sort List

Given the head of a linked list, sort the list in ascending order and return the sorted head.

Why this is worth learning

Merge sort fits linked lists because merging advances pointers, whereas indexed partitioning would repeatedly scan. A recursive split must physically cut the list so each call owns a smaller disjoint chain.

Before coding: one-minute experiment

Why does merely finding slow at the middle, without setting the predecessor Next to nil, fail to make recursive progress?

Function signature

func SortList(head *ListNode) *ListNode

Inputs / outputs

• head: head of a singly linked list.
• Return: head of the sorted list.

Example

Input: 4 -> 2 -> 1 -> 3
Output: 1 -> 2 -> 3 -> 4

Constraints

• 0 <= number of nodes <= 50_000; the input chain is acyclic.
• Reuse each original node exactly once without changing its Val. Rewire Next pointers into a sorted, acyclic chain.
• Preserve the original order of equal-valued nodes (stable sorting).

Core idea (near-solution)

Use merge sort. Split the list into halves with slow/fast pointers, recursively sort both halves, then merge two sorted lists.

Invariant: SortList(head) returns a sorted list containing exactly the nodes from the original list starting at head.

Algorithm (step-by-step)

1. If the list has zero or one node, return it.
2. Use slow/fast pointers to find the midpoint.
3. Cut the list into two independent halves.
4. Recursively sort each half.
5. Merge the two sorted halves using a dummy head.
6. Return the merged list.

Correctness sketch

For zero or one node the list is already sorted. Otherwise slow/fast traversal finds a middle and cutting prev.Next splits the original nodes into two nonempty smaller lists. By induction recursive calls return sorted chains containing exactly their respective nodes. The merge repeatedly appends the smaller head; no later node in either sorted chain can be smaller, so the output prefix stays sorted. Appending the remaining suffix completes the union without allocating replacement data nodes. Choosing from the left on equality preserves original relative order of equal values. Disjoint sublists and complete rewiring prevent cycles and node loss.

Trace (hand walkthrough)

4->2->1->3
split: 4->2 and 1->3
sort: 2->4 and 1->3
merge: 1->2->3->4

Pitfalls to avoid

• Forgetting to cut the list at the midpoint, causing infinite recursion.
• Losing the second half while rewiring pointers.
• Allocating new nodes unnecessarily.

Debugging lens

Test exact node membership and cycle absence, not just sorted values. A value-only rewrite can conceal losing nodes. Include two-node and all-equal lists to expose bad split termination.

Complexity

• Time: O(n log n).
• Extra space: O(log n) recursion depth.

Implementation notes (Go)

• Use prev to cut before slow.
• The merge step reuses existing nodes; choose the left head on equal values to retain stability.

Reconstruction checkpoint

Why does merely finding slow at the middle, without setting the predecessor Next to nil, fail to make recursive progress?

Return to Divide & Conquer · Module quiz