Sort List Solution

Problem

Given the head of a singly linked list, sort it in ascending order. The challenge is to do it in O(n log n) time — ruling out simple O(n²) approaches like selection sort — and the follow-up asks for O(1) auxiliary space, which rules out copying nodes into an array.

→

→∅

[4,2,1,3]

Input: head = [4, 2, 1, 3]
Output: [1, 2, 3, 4]
Explanation: Nodes are rewired so each value is less than or equal to the next.

Intuition

Merge sort is the natural fit: split the list in half, recursively sort each half, then merge the two sorted halves. Unlike arrays, linked lists let you merge two sorted halves without any extra buffer — you just rewire pointers. The two key sub-problems are finding the midpoint with the slow/fast pointer technique and merging two sorted lists (a standalone LeetCode problem in its own right).

Approach 1 — Recursive (Top-Down Merge Sort)

Use slow/fast pointers to find the midpoint, sever the list at that point, recursively sort each half, then merge. The most readable approach, though the recursion depth costs O(log n) stack space.

Base case: return immediately if the list is empty or has one node — already sorted.
Walk slow one step and fast two steps simultaneously until fast reaches the end.
Sever: set slow.next = None to split the list at the midpoint into two independent halves.
Recursively sort the left half (from head) and the right half (from mid).
Merge the two sorted halves and return the merged head.

1class Solution:
2    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
3        if not head or not head.next:
4            return head
5
6        # starting fast at head.next ensures slow lands at the last node of the left half
7        slow, fast = head, head.next
8        while fast and fast.next:
9            slow = slow.next
10            fast = fast.next.next
11
12        mid = slow.next
13        slow.next = None  # sever so the left half doesn't reference the right
14
15        left = self.sortList(head)
16        right = self.sortList(mid)
17        return self._merge(left, right)
18
19    def _merge(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
20        dummy = ListNode(0)
21        current = dummy
22        while l1 and l2:
23            if l1.val <= l2.val:
24                current.next = l1
25                l1 = l1.next
26            else:
27                current.next = l2
28                l2 = l2.next
29            current = current.next
30        current.next = l1 or l2  # attach whichever list still has remaining nodes
31        return dummy.next

Time: O(n log n) — the list is halved at each level (log n levels) and each level does O(n) work during the merge phase.
Space: O(log n) — the recursion stack grows one frame per level, and there are log n levels.

Approach 2 — Iterative (Bottom-Up Merge Sort)

Simulate merge sort without recursion by starting with chunk size 1 and doubling each pass. In each pass, adjacent pairs of chunks are merged. After O(log n) passes the full list is sorted, and no call stack is needed.

Count the list length so you know when to stop doubling the chunk size.
Create a dummy sentinel head to simplify pointer updates at the front of each merged result.
For each chunk size (1, 2, 4, …), scan the list left to right using current.
In each inner iteration: detach one left chunk and one right chunk using a helper, merge them, and link the merged result onto the growing sorted tail.
Double the chunk size and repeat until chunks exceed the list length.

1class Solution:
2    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
3        length, node = 0, head
4        while node:
5            length += 1
6            node = node.next
7
8        dummy = ListNode(0)
9        dummy.next = head
10        chunk_size = 1
11
12        while chunk_size < length:
13            current = dummy.next
14            tail = dummy  # end of the sorted portion built so far this pass
15
16            while current:
17                left = current
18                right = self._cut(left, chunk_size)    # detach left chunk; right begins here
19                current = self._cut(right, chunk_size)  # detach right chunk; next pair begins here
20
21                merged_head, merged_tail = self._merge(left, right)
22                tail.next = merged_head
23                tail = merged_tail  # must track the true tail to link the next merged pair
24
25            chunk_size <<= 1  # double for the next pass
26
27        return dummy.next
28
29    def _cut(self, head: Optional[ListNode], size: int) -> Optional[ListNode]:
30        for _ in range(size - 1):  # advance size-1 times to reach the last node of this chunk
31            if head:
32                head = head.next
33        if not head:
34            return None
35        remainder = head.next
36        head.next = None  # sever: this chunk now ends here
37        return remainder
38
39    def _merge(self, l1: Optional[ListNode], l2: Optional[ListNode]):
40        dummy = ListNode(0)
41        current = dummy
42        while l1 and l2:
43            if l1.val <= l2.val:
44                current.next = l1
45                l1 = l1.next
46            else:
47                current.next = l2
48                l2 = l2.next
49            current = current.next
50        current.next = l1 or l2
51        while current.next:  # walk to the true end of the merged chain
52            current = current.next
53        return dummy.next, current

Time: O(n log n) — O(log n) passes over the full list, each costing O(n) work.
Space: O(1) — only a constant number of pointer variables; no recursion stack.

Complexity Summary

Approach	Time	Space	When to use
Recursive (Top-Down)	O(n log n)	O(log n)	When readability is the priority and the list isn't long enough to risk stack overflow
Iterative (Bottom-Up)	O(n log n)	O(1)	When the problem explicitly demands constant extra space

Common Mistakes

Not severing the list before recursing: After the slow/fast walk, you must set slow.next = None. Without this, the left half still points into the right half, so sortList(head) recurses on the entire original list — causing an infinite recursion or incorrect output.
Starting fast at head instead of head.next: If both pointers start at head, slow lands one step too far into the list for even-length inputs. Starting fast at head.next ensures slow stops at the last node of the left half, giving a clean equal-sized split.
Off-by-one in the cut helper: The helper should advance size - 1 steps and then sever at head.next. Advancing size steps severs one node too late, so the left chunk contains an extra node and the right chunk is one short.
Returning early from _merge without finding the true tail: After current.next = l1 or l2, the remaining chain may have many nodes. If you return current immediately as the tail, tail points to the interior of the list, and the next merged pair overwrites nodes that haven't been read yet.
Using sort() on a values array as a shortcut: Extracting values to an array, sorting, and writing back avoids the core pointer challenge the problem is testing. It also loses node identity, which matters if the nodes carry satellite data beyond their value.

Sort List — Solution