Sort List LeetCode Solution: Merge Sort on a Linked List

Sort List is one of those problems that pulls together everything you have learned about linked lists into a single, satisfying solution. LeetCode 148 asks you to sort a linked list in O(n log n) time and, ideally, O(1) auxiliary space. If you have practiced finding the middle of a list, splitting nodes, and merging two sorted lists, this problem is the final exam that tests all three skills at once.

The answer is merge sort — the only comparison-based sort that naturally fits linked list structure. Unlike array-based sorts that rely on random access, merge sort works entirely through sequential pointer manipulation. You split, recurse, and merge, and the list comes out sorted. This walkthrough breaks down every step so you can implement it from memory in your next interview.

If you are comfortable with Merge Two Sorted Lists (#21) and Middle of Linked List (#876), you already know 80% of the solution. Sort List simply composes those techniques inside a recursive divide-and-conquer framework.

You are given the head of a singly linked list. Return the head of the list after sorting it in ascending order. The problem asks for O(n log n) time complexity, and the follow-up challenge requests O(1) space — meaning you should avoid creating new nodes or using arrays.

The constraint on time complexity immediately narrows your options. Bubble sort and insertion sort are O(n^2). Counting sort and radix sort require known value ranges. That leaves merge sort, which delivers O(n log n) time and, on linked lists, requires only O(log n) stack space for the recursive calls.

The key insight is that linked lists make merge sort easier, not harder. You do not need to allocate extra arrays for the merge step because you can rewire pointers in place. The split step is also straightforward — find the middle node and set its next pointer to null.

On arrays, quicksort is usually the fastest practical sort because it benefits from cache locality and in-place partitioning with random access. But linked lists destroy both of those advantages. Accessing the k-th element of a linked list takes O(k) time, so the partition step in quicksort degrades badly. Heap sort similarly requires array indexing to maintain the heap property.

Merge sort, by contrast, only needs two operations that linked lists handle efficiently: finding the middle element (fast/slow pointer in O(n)) and merging two sorted sequences (pointer rewiring in O(n)). Every step of the algorithm walks through nodes sequentially, which is exactly what linked lists are designed for.

This is why sort list leetcode is considered a must-know problem. It demonstrates that the right algorithm choice depends on your data structure. An interviewer who asks this problem is testing whether you understand that constraint — not just whether you can write a sort.

The sort list algorithm has three core steps that repeat recursively: find the middle node, split the list into two halves, and merge the sorted halves back together. Here is how each step works.

First, use the fast and slow pointer technique to find the middle of the list. Initialize slow and fast to head. Move slow one step and fast two steps until fast reaches the end. When fast stops, slow points to the middle node. This is the same technique from Middle of Linked List (#876).

Second, split the list by saving slow.next as the head of the right half, then setting slow.next to null. This cleanly separates the list into two independent halves. Without this null termination, both halves share a tail and the recursion creates an infinite loop.

Third, recursively sort both halves, then merge them using the standard merge-two-sorted-lists procedure from LeetCode #21. Create a dummy node, compare the heads of both lists, and append the smaller node to the result. Continue until one list is exhausted, then attach the remaining nodes.

Let us trace through the algorithm with the input [4, 2, 1, 3]. The list starts as 4 -> 2 -> 1 -> 3 -> null.

Step 1: Find the middle. Slow lands on node 2, fast lands on node 3. Save slow.next (node 1) as rightHead. Set slow.next = null. Now we have two lists: [4, 2] and [1, 3].

Step 2: Recurse on [4, 2]. Find middle — slow lands on 4, fast lands on 2. Split into [4] and [2]. Both are single nodes (base case), so merge them: compare 4 and 2, result is 2 -> 4.

Step 3: Recurse on [1, 3]. Find middle — slow lands on 1, fast lands on 3. Split into [1] and [3]. Merge: compare 1 and 3, result is 1 -> 3.

Step 4: Merge [2, 4] and [1, 3]. Compare 2 and 1 — take 1. Compare 2 and 3 — take 2. Compare 4 and 3 — take 3. Take 4. Final result: 1 -> 2 -> 3 -> 4. The list is sorted.

Time complexity is O(n log n). Each level of recursion processes all n nodes during the merge step, and there are log n levels because we halve the list each time. Space complexity is O(log n) due to the recursive call stack. The iterative bottom-up version achieves true O(1) space but is significantly harder to implement and rarely expected in interviews.

Edge cases to consider: a single node returns immediately (base case). Two nodes require one comparison and a swap if needed. An already sorted list still goes through the full split-merge process but produces the same order. A reverse-sorted list is the worst case for comparisons during merge but does not change the time complexity. A list where all values are equal merges trivially since every comparison results in taking the left node.

Sort List is a synthesis problem. It does not introduce any new technique — instead, it tests whether you can compose familiar building blocks into a complete algorithm. Finding the middle, splitting a list, and merging two sorted lists are each straightforward on their own. The challenge is combining them cleanly inside a recursive framework without off-by-one errors or missing null terminations.

This is exactly the kind of problem that separates candidates who memorize solutions from those who understand patterns. If you have internalized the fast/slow pointer from #876 and the merge procedure from #21, Sort List becomes a 15-minute problem instead of a 45-minute struggle.

Practice recognizing this composition pattern with YeetCode flashcards. When you can recall the three sub-techniques and assemble them from memory, you are ready not just for Sort List but for any linked list problem that combines divide and conquer with pointer manipulation.