97. Sort List
🔗 LeetCode Problem: 148. Sort List
📊 Difficulty: Medium
🏷️ Topics: Linked List, Two Pointers, Divide and Conquer, Sorting, Merge Sort
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]
Visual:
Before: 4 → 2 → 1 → 3 → null
After: 1 → 2 → 3 → 4 → null
Example 2:
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Visual:
Before: -1 → 5 → 3 → 4 → 0 → null
After: -1 → 0 → 3 → 4 → 5 → null
Example 3:
Input: head = []
Output: []
Constraints:
- The number of nodes in the list is in the range [0, 5 * 10^4].
- -10^5 <= Node.val <= 10^5
Follow up: Can you sort the linked list in O(n log n) time and O(1) memory (i.e. constant space)?
🌟 ELI5: The Simple Idea!
Think of sorting playing cards using divide and conquer:
You have: [4, 2, 1, 3]
Divide:
Split into two piles:
[4, 2] and [1, 3]
Conquer:
Sort each pile:
[4, 2] → [2, 4]
[1, 3] → [1, 3]
Merge:
Combine sorted piles:
[2, 4] + [1, 3] → [1, 2, 3, 4] ✓
This is Merge Sort!
Why Merge Sort for linked lists?
✓ No random access needed (good for linked lists)
✓ O(n log n) time guaranteed
✓ Can be done in O(1) space (bottom-up)
✓ Stable sort
🎨 Visual Understanding
Merge Sort Process
Original: [4, 2, 1, 3]
═══════════════════════════════════════════════════════════════
Divide Phase (Top-Down)
═══════════════════════════════════════════════════════════════
Level 0: [4, 2, 1, 3]
Split at middle
↓
Level 1: [4, 2] [1, 3]
↓ ↓ ↓ ↓
Level 2: [4][2] [1][3]
═══════════════════════════════════════════════════════════════
Conquer Phase (Merge Up)
═══════════════════════════════════════════════════════════════
Level 2: Merge [4] and [2]
4 vs 2 → [2, 4]
Merge [1] and [3]
1 vs 3 → [1, 3]
Level 1: Merge [2, 4] and [1, 3]
2 vs 1 → take 1: [1]
2 vs 3 → take 2: [1, 2]
4 vs 3 → take 3: [1, 2, 3]
4 vs null → take 4: [1, 2, 3, 4]
Result: [1, 2, 3, 4] ✓
🎯 Approach 1: Top-Down Merge Sort (Recursive) ⭐
The Classic Solution
Algorithm:
Base case: List is null or single node → already sorted
Recursive case:
1. Find middle using fast & slow pointers
2. Split list into two halves
3. Recursively sort both halves
4. Merge sorted halves
Implementation
/**
* Top-down merge sort (recursive)
* Time: O(n log n), Space: O(log n) - recursion stack
*/
public ListNode sortList(ListNode head) {
// Base case: empty or single node
if (head == null || head.next == null) {
return head;
}
// Step 1: Find middle and split
ListNode mid = getMid(head);
ListNode left = head;
ListNode right = mid.next;
mid.next = null; // Break the link
// Step 2: Recursively sort both halves
left = sortList(left);
right = sortList(right);
// Step 3: Merge sorted halves
return merge(left, right);
}
private ListNode getMid(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// Find middle (slow ends at first middle for even length)
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
⏰ Time: O(n log n) - T(n) = 2T(n/2) + O(n)
💾 Space: O(log n) - Recursion call stack
🔍 Super Detailed Dry Run
Example: head = [4, 2, 1, 3]
Goal: Sort to [1, 2, 3, 4]
═══════════════════════════════════════════════════════════════
Recursion Tree
═══════════════════════════════════════════════════════════════
sortList([4, 2, 1, 3])
↓
Find mid: slow at 2
Split: left=[4,2], right=[1,3]
↓
├─ sortList([4, 2])
│ ↓
│ Find mid: slow at 4
│ Split: left=[4], right=[2]
│ ↓
│ ├─ sortList([4])
│ │ Base case: return [4]
│ │
│ └─ sortList([2])
│ Base case: return [2]
│
│ Merge [4] and [2]
│ 4 vs 2 → [2]
│ 4 vs null → [2, 4]
│ Return [2, 4]
│
└─ sortList([1, 3])
↓
Find mid: slow at 1
Split: left=[1], right=[3]
↓
├─ sortList([1])
│ Base case: return [1]
│
└─ sortList([3])
Base case: return [3]
Merge [1] and [3]
1 vs 3 → [1]
null vs 3 → [1, 3]
Return [1, 3]
Merge [2, 4] and [1, 3]
2 vs 1 → take 1: [1]
2 vs 3 → take 2: [1, 2]
4 vs 3 → take 3: [1, 2, 3]
4 vs null → [1, 2, 3, 4]
Return [1, 2, 3, 4]
═══════════════════════════════════════════════════════════════
Detailed Merge Example: [2, 4] + [1, 3]
═══════════════════════════════════════════════════════════════
l1: 2 → 4 → null
l2: 1 → 3 → null
dummy → null
curr = dummy
Iteration 1:
l1.val (2) vs l2.val (1)
1 < 2, take l2
curr.next = l2 (node 1)
l2 = l2.next (node 3)
curr = curr.next (node 1)
Result: dummy → 1
l1: 2 → 4
l2: 3 → null
Iteration 2:
l1.val (2) vs l2.val (3)
2 < 3, take l1
curr.next = l1 (node 2)
l1 = l1.next (node 4)
curr = curr.next (node 2)
Result: dummy → 1 → 2
l1: 4 → null
l2: 3 → null
Iteration 3:
l1.val (4) vs l2.val (3)
3 < 4, take l2
curr.next = l2 (node 3)
l2 = l2.next (null)
curr = curr.next (node 3)
Result: dummy → 1 → 2 → 3
l1: 4 → null
l2: null
Iteration 4:
l2 = null, exit loop
Attach remaining:
curr.next = l1 (node 4)
Result: dummy → 1 → 2 → 3 → 4
Return dummy.next: [1, 2, 3, 4] ✓
🎯 Approach 2: Bottom-Up Merge Sort (O(1) Space) ⭐⭐
The Space-Optimized Solution
Algorithm:
Instead of recursion, build sorted sublists iteratively:
size = 1: Merge pairs of size 1
size = 2: Merge pairs of size 2
size = 4: Merge pairs of size 4
...
Until entire list is sorted
Implementation
/**
* Bottom-up merge sort (iterative)
* Time: O(n log n), Space: O(1)
*/
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// Get length
int length = 0;
ListNode curr = head;
while (curr != null) {
length++;
curr = curr.next;
}
// Dummy node for result
ListNode dummy = new ListNode(0);
dummy.next = head;
// Bottom-up merge
for (int size = 1; size < length; size *= 2) {
ListNode tail = dummy;
curr = dummy.next;
while (curr != null) {
ListNode left = curr;
ListNode right = split(left, size);
curr = split(right, size);
tail = merge(tail, left, right);
}
}
return dummy.next;
}
// Split list into first n nodes and rest
// Returns the head of the rest
private ListNode split(ListNode head, int n) {
while (head != null && n > 1) {
head = head.next;
n--;
}
if (head == null) return null;
ListNode rest = head.next;
head.next = null;
return rest;
}
// Merge two sorted lists and attach to tail
// Returns the new tail
private ListNode merge(ListNode tail, ListNode l1, ListNode l2) {
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
while (tail.next != null) {
tail = tail.next;
}
return tail;
}
⏰ Time: O(n log n)
💾 Space: O(1) - Only pointers, no recursion
Visual Bottom-Up Process
Original: [4, 2, 1, 3]
Size = 1: Merge pairs of 1
[4] + [2] → [2, 4]
[1] + [3] → [1, 3]
Result: [2, 4, 1, 3]
Size = 2: Merge pairs of 2
[2, 4] + [1, 3] → [1, 2, 3, 4]
Result: [1, 2, 3, 4] ✓
Done! Size (4) >= length (4)
🎯 Key Insights
Insight 1: Why Merge Sort for Linked Lists?
Arrays vs Linked Lists:
Arrays:
QuickSort: O(n log n) average, O(1) space ✓
MergeSort: O(n log n) always, O(n) space ✗
Linked Lists:
QuickSort: O(n log n) average, but hard to implement
MergeSort: O(n log n) always, O(1) space! ✓
Why MergeSort wins:
✓ No random access needed
✓ Natural split at middle
✓ Merge is just pointer manipulation
✓ Bottom-up gives O(1) space
Insight 2: Finding Middle (Key Step)
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
Why fast.next.next?
Ensures slow at FIRST middle for even length
[1, 2, 3, 4]
slow ends at 2 (first middle)
Split: [1, 2] and [3, 4]
Balanced split! ✓
Insight 3: Time Complexity
Merge Sort Recurrence:
T(n) = 2 * T(n/2) + O(n)
2 * T(n/2): Sort two halves
O(n): Merge step
Master Theorem:
a = 2, b = 2, f(n) = n
log_b(a) = log_2(2) = 1
f(n) = n^1
Case 2: T(n) = O(n log n)
Levels in recursion tree:
Each level divides by 2
log_2(n) levels
Each level does O(n) work
Total: O(n log n) ✓
⚠️ Common Mistakes
Mistake 1: Not breaking link when splitting
// ❌ WRONG - Left list still connects to right!
ListNode mid = getMid(head);
ListNode right = mid.next;
// Forgot: mid.next = null
// This creates issues during merge!
// ✓ CORRECT - Break the link
mid.next = null;
Mistake 2: Wrong middle finding condition
// ❌ WRONG - For even length, slow goes too far
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// [1, 2, 3, 4] → slow at 3 (second middle)
// Unbalanced: [1, 2, 3] and [4]
// ✓ CORRECT
while (fast.next != null && fast.next.next != null) {
// ...
}
// slow at 2 (first middle)
// Balanced: [1, 2] and [3, 4]
Mistake 3: Forgetting base case
// ❌ WRONG - Infinite recursion!
public ListNode sortList(ListNode head) {
ListNode mid = getMid(head);
// ... recursive calls without base case
}
// ✓ CORRECT - Base case first!
if (head == null || head.next == null) {
return head;
}
Mistake 4: Modifying merge from LC 21
// Merge for arrays creates new array
// But for linked lists, reuse nodes!
// ✓ CORRECT - Reuse existing nodes
curr.next = l1; // Don't create new!
l1 = l1.next;
Mistake 5: Using insertion/bubble sort
// ❌ WRONG - O(n²) time!
// Sorts but doesn't meet O(n log n) requirement
// ✓ CORRECT - Use merge sort
// O(n log n) guaranteed
🎯 Pattern Recognition
Problem Type: Sort Linked List in O(n log n)
Core Pattern: Merge Sort (Top-Down or Bottom-Up)
When to Apply:
✓ Sort linked list efficiently
✓ Need O(n log n) time
✓ Want stable sort
✓ No random access available
Recognition Keywords:
- "sort linked list"
- "O(n log n)"
- "ascending/descending order"
- "stable sort"
Similar Problems:
- Merge Two Sorted Lists (LC 21) - Used as subroutine
- Merge k Sorted Lists (LC 23) - Extended version
- Sort Colors (LC 75) - Different approach (counting)
Key Components:
┌────────────────────────────────────────────┐
│ Algorithm: Merge Sort │
│ Find Middle: Fast & Slow Pointers │
│ Merge: Two-pointer merge (LC 21) │
│ Top-Down: O(log n) space (recursion) │
│ Bottom-Up: O(1) space (iterative) │
│ Time: O(n log n) guaranteed │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "I need to sort in O(n log n) time"
Step 2: "Merge sort is ideal for linked lists"
Step 3: "I'll use find middle + recursive sort + merge"
Key Points to Mention:
- Merge sort chosen for O(n log n) guarantee
- No random access → merge sort better than quicksort
- Three components: find middle, sort halves, merge
- Each component is O(n), log n levels
- Space: O(log n) recursive, O(1) bottom-up
- Reuses existing nodes (no new allocation)
Walk Through Example:
"For [4,2,1,3]:
Find middle at 2, split into [4,2] and [1,3]
Recursively sort both: [2,4] and [1,3]
Merge sorted halves:
2 vs 1 → take 1
2 vs 3 → take 2
4 vs 3 → take 3
4 → take 4
Result: [1,2,3,4]"
Complexity Analysis:
"Find middle: O(n)
Sort each half: T(n/2)
Merge: O(n)
Recurrence: T(n) = 2T(n/2) + O(n) = O(n log n)
Space: O(log n) for recursion stack"
Follow-up (O(1) space):
"Can use bottom-up merge sort:
Start with pairs of 1, then 2, then 4...
No recursion needed, O(1) extra space
Same time complexity O(n log n)"
Edge Cases to Mention:
✓ Empty list → return null
✓ Single node → already sorted
✓ Two nodes → one comparison
✓ Already sorted → still O(n log n)
✓ Reverse sorted → still O(n log n)
📝 Quick Revision Notes
🎯 Core Concept:
Sort List: Use merge sort for O(n log n). Top-down: (1) Find middle with fast & slow, (2) Recursively sort halves, (3) Merge sorted halves. Bottom-up: Merge pairs of size 1, then 2, then 4... O(1) space! Break link after finding middle. Merge reuses existing nodes.
⚡ Quick Implementation (Top-Down):
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public static ListNode create(List<Integer> list) {
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
for(int num : list) {
curr.next = new ListNode(num);
curr = curr.next;
}
return dummy.next;
}
public static void print(ListNode head) {
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + " -> ");
curr = curr.next;
}
System.out.println();
}
public ListNode sortList(ListNode head) {
// empty or single node lists.
if(head == null || head.next == null) {
return head;
}
// Identify middle node to split (slow ends at first middle for even length)
// 2 in case of [4,2,1,3] and 3 in case of [-1,5,3,4,0]
ListNode middleNode = getMiddleNode(head);
// Separating the lists to eqal halves for divide and conquer or merge sorting.
ListNode second = middleNode.next;
ListNode first = head;
middleNode.next = null; // cut both halves
// Sort these 2 halves separately.
first = sortList(first);
second = sortList(second);
// Merge these 2 sorted lists.
head = sort(first, second);
return head;
}
private ListNode sort(ListNode first, ListNode second) {
ListNode dummy = new ListNode();
ListNode curr = dummy;
while (first != null && second != null) {
if(first.val < second.val) {
curr.next = new ListNode(first.val);
first = first.next;
} else {
curr.next = new ListNode(second.val);
second = second.next;
}
curr = curr.next;
}
// while (first != null) {
// curr.next = new ListNode(first.val);
// curr = curr.next;
// first = first.next;
// }
if(first != null) {
curr.next = first;
}
// while (second != null) {
// curr.next = new ListNode(second.val);
// curr = curr.next;
// second = second.next;
// }
if(second != null) {
curr.next = second;
}
return dummy.next;
}
private ListNode getMiddleNode(ListNode head) {
// 2 in case of [4,2,1,3] and 3 in case of [-1,5,3,4,0]
ListNode slow = head;
ListNode fast = head.next; // this is crucial hack we have done for getting mid node correctly
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public static void main(String[] args) {
Solution t = new Solution();
ListNode list1 = create(Arrays.asList(4, 2, 1, 3));
print(t.sortList(list1));
print(t.sortList(create(Arrays.asList(-1, 5, 3, 4, 0))));
print(t.sortList(create(Arrays.asList(0)))); // 1 element
print(t.sortList(create(Arrays.asList(0, 1)))); // 2 elements
print(t.sortList(create(Arrays.asList(2, 1)))); // 2 elements
print(t.sortList(create(Arrays.asList(2, 1, 5)))); // odd count
print(t.sortList(create(Arrays.asList(2, 1, -4, 0)))); // even count
print(t.sortList(create(Arrays.asList(1, 2, 3, 4, 5)))); // strictly increasing
print(t.sortList(create(Arrays.asList(5, 4, 3, 2)))); // strictly decreasing
}
}
🔑 Key Insights:
- Pattern: Merge Sort (Divide & Conquer)
- Three steps: Find middle, sort halves, merge
- Break link: mid.next = null (critical!)
- Middle: Use fast.next.next condition
- Merge: Reuse nodes from LC 21
- Time: O(n log n), Space: O(log n) or O(1) ✓
🎪 Memory Aid:
"Divide in half, sort each, merge together!"
"Middle → Sort → Merge!" ✨
⚡ Complexity:
Recurrence: T(n) = 2T(n/2) + O(n)
Tree:
Level 0: n work (merge)
Level 1: n work (2 merges of n/2)
Level 2: n work (4 merges of n/4)
...
log n levels
Total: n * log n = O(n log n) ✓
Space:
Top-down: O(log n) recursion
Bottom-up: O(1) iterative
🧪 Edge Cases
Case 1: Empty list
Input: head = null
Output: null
Handled: Base case
Case 2: Single node
Input: head = [1]
Output: [1]
Handled: Base case
Case 3: Two nodes
Input: head = [2,1]
Output: [1,2]
Handled: One split, one merge
Case 4: Already sorted
Input: head = [1,2,3,4,5]
Output: [1,2,3,4,5]
Time: Still O(n log n) (not adaptive)
Case 5: Reverse sorted
Input: head = [5,4,3,2,1]
Output: [1,2,3,4,5]
Time: Still O(n log n)
All handled correctly! ✓
Related Problems
- Merge Two Sorted Lists (LC 21) - Building block
- Merge k Sorted Lists (LC 23) - Extension
- Insertion Sort List (LC 147) - Different approach (O(n²))
- Sort Colors (LC 75) - Array sorting
Happy practicing! 🎯
Note: This problem teaches merge sort on linked lists - a fundamental divide-and-conquer algorithm! The key insight is that merge sort is IDEAL for linked lists because: (1) no random access needed, (2) natural merge operation, (3) can achieve O(1) space with bottom-up. This is THE standard way to sort a linked list efficiently! 💪✨