Sort List LeetCode 148 — Merge Sort

LeetCode 148 — Sort List — gives you the head of a singly linked list and asks you to return the head of the list sorted in ascending order. The expected time complexity is O(n log n), which rules out insertion sort (O(n²)) and bubble sort. The follow-up challenge is to achieve O(1) extra space — no recursion stack allowed — which rules out the naive top-down recursive solution unless you use the bottom-up iterative variant.

Unlike arrays, linked lists do not support random access. You cannot read the element at index k in O(1) time — you must traverse from the head each time. This means algorithms like heapsort and quicksort that rely on random access become inefficient or awkward on linked lists. Merge sort, however, works beautifully on linked lists because it only requires sequential access: split at the middle using fast/slow pointers, and merge using pointer rewiring instead of copying into a temporary array.

The problem is also a composition of two prerequisite problems you have likely already solved: LeetCode 876 (Middle of Linked List) provides the fast/slow pointer midpoint technique, and LeetCode 21 (Merge Two Sorted Lists) provides the merge step. Recognizing Sort List as a composition of these two building blocks is the key insight that transforms a hard problem into a structured engineering exercise.

Quicksort needs random access to partition efficiently. In the array version, you can swap elements at arbitrary indices in O(1). On a linked list, reaching the k-th node costs O(k) time, making the partitioning step O(n) per level in the best case but with poor cache behavior and complex pointer rewiring. Merge sort avoids random access entirely: splitting at the middle requires only one O(n) traversal, and merging two sorted lists requires only sequential pointer comparisons.

The split step uses the fast/slow pointer technique. Start both pointers at the head; advance fast two steps and slow one step each iteration. When fast reaches the end, slow is at the midpoint. Disconnect the first half from the second by setting slow.next = null. This gives you two halves of approximately equal length in O(n) time without knowing the list length in advance.

The merge step rewires pointers in-place. Compare the heads of the two sorted halves, attach the smaller one to the growing result, and advance that pointer. No extra array is needed — you reuse the existing nodes by changing their next pointers. This is why merge sort achieves O(1) auxiliary space per merge level, and why the overall space can be reduced to O(1) with the bottom-up iterative approach that eliminates the recursion stack entirely.

The top-down approach is the natural recursive formulation. Base cases: if the head is null or head.next is null, the list is already sorted — return head. Recursive case: find the middle, disconnect the two halves, recursively sort each half, then merge the two sorted halves. The recursion tree has O(log n) levels because each call splits the list approximately in half.

Finding the middle correctly requires disconnecting the first half before the recursive calls. After the fast/slow traversal, slow points to the last node of the first half. Save slow.next as the start of the second half, then set slow.next = null to disconnect. Without this disconnection, the recursive call on the first half would still have access to the second half via next pointers and the recursion would not terminate correctly.

Time complexity is O(n log n): there are O(log n) levels of recursion, and each level does O(n) total work across all merge operations at that level. Space complexity is O(log n) for the recursion call stack — one stack frame per level of the recursion tree. This is acceptable for most inputs but does not satisfy the O(1) space follow-up. Use the bottom-up approach for that.

The merge subroutine is identical to LeetCode 21 — Merge Two Sorted Lists. Create a dummy head node to simplify edge cases. Maintain a tail pointer starting at dummy. While both lists are non-null, compare their head values: attach the smaller-valued node to tail.next and advance that list's pointer. After one list is exhausted, attach the remaining nodes of the other list to tail.next (they are already sorted). Return dummy.next.

This merge runs in O(n) time where n is the total number of nodes across both lists. It uses O(1) auxiliary space — no array or extra nodes are allocated. All operations are pointer rewirings on existing nodes. The dummy node trick avoids special-casing the first node attachment and keeps the code clean.

Because merge is the inner operation of merge sort, its O(1) space is critical. At each level of the recursion tree, the total work is O(n) spread across all merges at that level. With O(log n) levels, the total time is O(n log n). The merge function is also idempotent and correct for empty inputs — if either list is null, the loop exits immediately and the other list is attached wholesale.

The bottom-up approach eliminates the recursion stack by iteratively merging sublists of increasing size. Start with sublists of size 1 (each node is trivially sorted). Merge adjacent pairs of size-1 sublists into sorted pairs of size 2. Then merge adjacent pairs of size 2 into sorted groups of size 4. Continue doubling the sublist size each round until the sublist size exceeds the length of the list — at that point the entire list is sorted.

Each round requires one pass over the list to merge all adjacent pairs of the current sublist size. Splitting a sublist of size k requires advancing k steps from the current position — no recursion, just pointer arithmetic. After merging a pair, the tail of the merged result is connected to the head of the next pair. A dummy head node simplifies managing the connections between merged segments.

Time complexity remains O(n log n): there are O(log n) rounds (sublist size doubles each round), and each round does O(n) total work. Space complexity is O(1) — no recursion stack, no auxiliary arrays. This satisfies the follow-up constraint exactly. The bottom-up approach is more complex to implement correctly because you must carefully track the tail of each merged segment and the start of the next unprocessed segment, but it is the production-quality answer for the follow-up.

Python top-down implementation: def sortList(head): if not head or not head.next: return head; slow, fast = head, head.next; while fast and fast.next: slow = slow.next; fast = fast.next.next; second = slow.next; slow.next = None; left = sortList(head); right = sortList(second); return merge(left, right). The getMid helper uses fast starting at head.next so slow stops at the last node of the first half, not the first node of the second half — this ensures correct splitting for odd-length lists.

Java top-down implementation: public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode second = slow.next; slow.next = null; return merge(sortList(head), sortList(second)); } The merge function uses a dummy node: ListNode dummy = new ListNode(0), tail = dummy; while both non-null compare and attach; attach remainder; return dummy.next.

Python bottom-up implementation: compute length, then for size in [1, 2, 4, ...] while size < length: iterate through list splitting pairs of size sublists, merging each pair, connecting tails. The split helper advances k steps and severs the connection, returning the start of the next segment. Both top-down and bottom-up are O(n log n) time; bottom-up is O(1) space while top-down is O(log n) stack space.

Merge Two Sorted Lists (LeetCode 21) is the direct prerequisite — it is the merge subroutine of Sort List verbatim. Merge K Sorted Lists (LeetCode 23) extends the merge step to k lists simultaneously using a min-heap or divide-and-conquer pairwise merging. The divide-and-conquer approach for LeetCode 23 is essentially the same merge sort structure applied to an array of list heads rather than to a single list.

Insertion Sort List (LeetCode 147) sorts a linked list using insertion sort in O(n²) time. It is simpler to implement but does not meet the O(n log n) requirement of LeetCode 148. Comparing these two problems illustrates why algorithm choice matters: insertion sort is natural for nearly-sorted inputs but degrades badly on random or reversed inputs, while merge sort maintains O(n log n) regardless of input order.

The linked list sort family — LeetCode 21, 23, 147, 148 — is a complete picture of sorting on sequential-access data structures. Mastering all four gives you fluency with merge operations, heap-based k-way merging, and the contrast between quadratic and log-linear sorting on linked lists. Sort List (148) is the capstone problem of this family and frequently appears in senior-level interviews at top technology companies.