Sort List - Solution & Explanation
Problem Statement
Given the head of a linked list, return the list after sorting it in ascending order.
Example 1:
Input: head = [4,2,1,3] Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5]
Example 3:
Input: head = [] Output: []
Constraints:
- The number of nodes in the list is in the range
[0, 5 * 104]. -105 <= Node.val <= 105
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Approach Overview
Problem Overview: Given the head of a singly linked list, you must return the list sorted in ascending order. The challenge is sorting efficiently while working with linked list constraints—no random access and minimal extra space.
Approach 1: Copy to Array and Sort (O(n log n) time, O(n) space)
The simplest strategy converts the linked list into an array, sorts the array using a standard algorithm like quicksort or mergesort, and then rebuilds the linked list. You iterate through the list once to collect values, apply the built-in array sort, then iterate again to recreate nodes in sorted order. This approach works because arrays support efficient sorting and random access. However, it uses O(n) additional memory and ignores the structural advantages of a linked list, so it’s rarely the preferred interview solution.
Approach 2: Merge Sort on Linked List (O(n log n) time, O(log n) space)
Merge sort is the natural fit for linked lists. The algorithm repeatedly splits the list into two halves using the fast and slow pointer technique, a classic two pointers pattern. Each half is recursively sorted, then merged using a standard sorted-merge routine that compares node values and relinks pointers. Because merging two linked lists only requires pointer updates, it runs in linear time. The recursion depth contributes O(log n) stack space. This divide and conquer strategy guarantees O(n log n) time while avoiding expensive node reallocations.
Approach 3: Bottom-Up Merge Sort (O(n log n) time, O(1) space)
The bottom-up version removes recursion and performs iterative merges. You start by merging pairs of nodes (size = 1), then merge sorted blocks of size 2, 4, 8, and so on until the entire list is sorted. Each pass walks the list, splitting segments and merging them in place. Since it doesn’t rely on recursive calls, the algorithm maintains constant auxiliary space while preserving the same O(n log n) time complexity. This approach is commonly labeled as merge sort optimized for linked lists and is the most space-efficient implementation.
Recommended for interviews: Top-down merge sort is the most common answer. It clearly demonstrates understanding of linked list traversal, splitting with fast/slow pointers, and merging sorted lists. Bottom-up merge sort is even more optimal in space, but interviewers usually expect the recursive version unless the problem explicitly asks for constant space.
Approach 1: Merge Sort on Linked List
This approach leverages the merge sort algorithm, which is well-suited for linked lists compared to arrays. The merge sort algorithm uses a divide-and-conquer strategy: it splits the list in half recursively until it can no longer be divided, and then merges the sublists back together in sorted order.
The C implementation uses two primary functions: sortList for recursively dividing and sorting the list, and merge for merging two sorted lists. The function splits the list using a slow-fast pointer method to find the midpoint, then recursively sorts each half, and finally merges the sorted halves. The dummy node is utilized to simplify merging logic.
Complexity
Time Complexity: O(n log n), where n is the number of nodes in the list. Space Complexity: O(log n) due to recursive stack space.
Approach 2: Bottom-Up Merge Sort for Linked List
This approach implements an iterative, bottom-up merge sort, avoiding the recursion and thus achieving O(1) space complexity beyond the input and output list. The list isn't split recursively but is treated progressively as sublists of increasing sizes are sorted and merged.
This C implementation of the bottom-up merge sort iteratively increases the block size for merging. It calculates the size n of the list first. Using a dummy node, it repeatedly splits the list into sublists of increasing size and merges them until the entire list is sorted.
Complexity
Time Complexity: O(n log n) where n is the number of nodes. Space Complexity: O(1).
Approach 3: Merge Sort
We can use the merge sort approach to solve this problem.
First, we use the fast and slow pointers to find the middle of the linked list and break the list from the middle to form two separate sublists l1 and l2.
Then, we recursively sort l1 and l2, and finally merge l1 and l2 into a sorted linked list.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the linked list.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Merge Sort on Linked List | Time Complexity: O(n log n), where n is the number of nodes in the list. Space Complexity: O(log n) due to recursive stack space. |
| Bottom-Up Merge Sort for Linked List | Time Complexity: O(n log n) where n is the number of nodes. Space Complexity: O(1). |
| Merge Sort | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Copy List to Array and Sort | O(n log n) | O(n) | Quick implementation when extra memory is acceptable |
| Top-Down Merge Sort | O(n log n) | O(log n) | Standard interview solution for sorting linked lists |
| Bottom-Up Merge Sort | O(n log n) | O(1) | Best when constant extra space is required |
Video Solution
Sort List - Merge Sort - Leetcode 148 • NeetCode • 102,611 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sort List easy or hard?
Sort List Python/Java solution
How to solve Sort List in O(n)?
What is the best approach for Sort List?
Is Sort List asked at Google/Amazon/Meta?
What data structure is used in Sort List?
What is the time complexity of Sort List?
Ready to solve this problem?
Practice Sort List with our built-in code editor and test cases.
Practice on FleetCode