Sort List
Understanding the Problem
We need to sort a singly linked list in ascending order. Unlike arrays, we cannot access elements by index, so algorithms like quicksort, which rely on random access for efficient partitioning, do not translate well. The sort has to work with sequential access only.
Merge sort fits linked lists well. On arrays, the merge step needs an O(n) temporary buffer to combine two sorted halves. On a linked list, the same merge step rearranges existing pointers, so it costs O(1) extra space. The one part that needs care is finding the middle of the list to split it, and a slow-fast pointer walk does that in O(n).
Key Constraints:
0 <= n <= 5 * 10^4→ With up to 50,000 nodes, an O(n^2) approach like insertion sort or bubble sort would be around 2.5 billion operations in the worst case. That's too slow. We need O(n log n).-10^5 <= Node.val <= 10^5→ Values fit comfortably in a 32-bit integer. No overflow concerns.- Follow-up asks for O(1) space → The basic recursive merge sort uses O(log n) stack space. The follow-up pushes us toward a bottom-up iterative merge sort.
Approach 1: Brute Force (Convert to Array)
Intuition
Sidestep the linked list constraints entirely. Copy all values into an array, sort the array with a built-in sort, then write the sorted values back into the nodes in order. The node structure never changes, only the values stored in it.
This is correct and easy to write, but it uses O(n) extra space for the array, which the follow-up asks us to avoid.
Algorithm
- Traverse the linked list and collect all node values into an array.
- Sort the array.
- Traverse the linked list again, overwriting each node's value with the next value from the sorted array.
- Return the head.
Example Walkthrough
Input:
After collecting values and sorting: [1, 2, 3, 4]. Write sorted values back to nodes:
Code
- Time Complexity: O(n log n). Collecting values is O(n). Sorting the array is O(n log n). Writing values back is O(n). The sorting step dominates.
- Space Complexity: O(n). We store all n values in an auxiliary array.
This works but uses O(n) extra space. The next approach sorts the nodes in place by rearranging pointers, using merge sort's divide-and-conquer structure.
Approach 2: Top-Down Merge Sort (Recursive)
Intuition
Apply merge sort's divide and conquer directly to the nodes: find the middle of the list with the slow-fast pointer technique, split the list into two halves, recursively sort each half, then merge the two sorted halves back together. The merge step links existing nodes instead of copying values, so it needs no temporary buffer.
Each recursion level splits every list in half, so the depth of the recursion is log(n) levels. At each level the merge steps together touch every node once, which is O(n) work per level. Multiplying the two gives O(n log n). The slow-fast walk that locates the midpoint is also O(n) per level, so it only adds a constant factor and does not change the bound.
Algorithm
- Base case: if the list is empty or has one node, it is already sorted. Return it.
- Find the middle node using slow and fast pointers.
- Split the list into two halves by setting the middle node's next to null.
- Recursively sort the left half and the right half.
- Merge the two sorted halves by comparing heads and linking nodes in order.
- Return the head of the merged list.
Example Walkthrough
Code
- Time Complexity: O(n log n). The list is halved at each recursion level (log n levels). At each level, the merge step processes all n nodes.
- Space Complexity: O(log n). The recursion stack goes log(n) deep. Each recursive call uses O(1) space. The merge itself is done in-place by rearranging pointers.
The O(log n) space comes from the recursion stack. To reach the O(1) space the follow-up asks for, the next approach removes the recursion and merges from the bottom up, starting with individual nodes and doubling the merge size each round.
Approach 3: Bottom-Up Merge Sort (Iterative, O(1) Space)
Intuition
The top-down approach splits the list in half recursively, which requires O(log n) stack space for the call stack. The bottom-up approach reverses the order of work. Instead of splitting first and merging on the way back up, it starts by treating every node as a sorted sublist of size 1, merges adjacent pairs into sorted sublists of size 2, then merges adjacent size-2 sublists into size-4 sublists, and so on.
Each pass walks all n nodes, and there are log(n) passes because the merge size doubles each time (1, 2, 4, up to n). The work iterates instead of recursing, so the only extra memory is a fixed set of pointers, giving O(1) space.
Algorithm
- Count the total number of nodes in the list.
- Start with merge size = 1.
- While merge size is less than the total count:
- Walk through the list, splitting off pairs of sublists of the current merge size.
- Merge each pair and attach the result to the growing sorted list.
- Double the merge size.
- Return the head of the sorted list.
Example Walkthrough
Code
- Time Complexity: O(n log n). We make log(n) passes over the list (merge size doubles each time: 1, 2, 4, ..., n). Each pass processes all n nodes during merging.
- Space Complexity: O(1). Only a constant number of pointer variables are used. No recursion, no auxiliary arrays.