Sort List

Sort a singly linked list in ascending order.

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 <= 100_000

Core idea (near-solution)

Use merge sort on a linked list. Find the middle with slow/fast pointers, split, sort each half, then merge.

Invariant: each recursive call returns a sorted list.

Algorithm (step-by-step)

1. Base case: if list has 0 or 1 node, return it.
2. Use slow/fast pointers to find the midpoint and split the list in half.
3. Recursively sort each half.
4. Merge the two sorted halves with a standard merge routine.
5. Return the merged list.

Correctness sketch

• Invariant: each recursive call returns a sorted list.
• The problem is split into independent subproblems.
• By induction, recursive solutions are correct.
• The combine step preserves correctness for the full problem.

Trace (hand walkthrough)

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

Walk:
- split: [4,2] and [1,3]
- sort halves -> [2,4] and [1,3]
- merge -> [1,2,3,4]

Pitfalls to avoid

• Forgetting to cut the list at the midpoint (creates cycles).
• Using extra arrays and losing O(1) space advantages.

Complexity

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

Implementation notes (Go)

• Keep a prev pointer while advancing slow/fast to split the list cleanly.
• Use a dummy head for merge.