76. Reorder List
🔗 LeetCode Problem: 143. Reorder List
📊 Difficulty: Medium
🏷️ Topics: Linked List, Two Pointers, Stack, Recursion
Problem Statement
You are given the head of a singly linked-list. The list can be represented as:
L₀ → L₁ → L₂ → L₃ → ... → Lₙ₋₁ → Lₙ
Reorder the list to be on the following form:
L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → ...
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Visual:
Before: 1 -> 2 -> 3 -> 4
After: 1 -> 4 -> 2 -> 3
Pattern: First, Last, Second, Second-Last
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Visual:
Before: 1 -> 2 -> 3 -> 4 -> 5
After: 1 -> 5 -> 2 -> 4 -> 3
Pattern: 1st, 5th, 2nd, 4th, 3rd
Constraints:
- The number of nodes in the list is in the range [1, 5 * 10^4].
- 1 <= Node.val <= 1000
🎨 Visual Understanding
The Problem Visualized
Example 1: [1,2,3,4]
Original:
1 -> 2 -> 3 -> 4 -> null
Reordered:
1 -> 4 -> 2 -> 3 -> null
↑ ↑ ↑ ↑
L₀ Lₙ L₁ Lₙ₋₁
Pattern: Alternate from start and end!
Example 2: [1,2,3,4,5]
Original:
1 -> 2 -> 3 -> 4 -> 5 -> null
Reordered:
1 -> 5 -> 2 -> 4 -> 3 -> null
↑ ↑ ↑ ↑ ↑
L₀ Lₙ L₁ Lₙ₋₁ L₂
Pattern: First, Last, Second, Second-Last, Middle
The Pattern:
Take first from start, then first from end
Take second from start, then second from end
Continue until all nodes used
Like shuffling two halves of a deck!
Original: [1, 2, 3, 4, 5, 6]
↑ ↑
start end
Split: [1, 2, 3] and [4, 5, 6]
Merge: 1 -> 6 -> 2 -> 5 -> 3 -> 4
↑ ↑ ↑ ↑ ↑ ↑
1st 6th 2nd 5th 3rd 4th
🚨 CRITICAL INSIGHT - Three-Step Algorithm!
The Key Pattern!
This problem combines THREE techniques:
1. Find Middle (Fast & Slow Pointers)
Split list into two halves
2. Reverse Second Half (Linked List Reversal)
Reverse the second half in-place
3. Merge Two Lists (Alternating)
Merge first half with reversed second half
Three steps = Three algorithms combined! 🎯
The Three-Step Strategy Visualized
Original: 1 -> 2 -> 3 -> 4 -> 5 -> 6
STEP 1: Find Middle & Split
First half: 1 -> 2 -> 3 -> null
Second half: 4 -> 5 -> 6 -> null
STEP 2: Reverse Second Half
First half: 1 -> 2 -> 3 -> null
Second half: 6 -> 5 -> 4 -> null (reversed!)
STEP 3: Merge Alternating
1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null
Result: Reordered! ✓
Detailed Step-by-Step Breakdown
Example: [1, 2, 3, 4, 5]
STEP 1: Find Middle
Use fast & slow pointers
slow ends at 3 (middle)
Split:
first: 1 -> 2 -> null (cut at middle)
second: 3 -> 4 -> 5 -> null
STEP 2: Reverse Second
Reverse: 3 -> 4 -> 5
Result: 5 -> 4 -> 3 -> null
Now we have:
first: 1 -> 2 -> null
second: 5 -> 4 -> 3 -> null
STEP 3: Merge
Take from first: 1
Take from second: 5
Take from first: 2
Take from second: 4
Take from first: null (done with first)
Take from second: 3
Result: 1 -> 5 -> 2 -> 4 -> 3 -> null ✓
Why This Pattern Works
The interleaving pattern:
L₀ → Lₙ → L₁ → Lₙ₋₁ → ...
Is equivalent to:
First half: L₀ → L₁ → L₂ → ...
Second half (reversed): Lₙ → Lₙ₋₁ → Lₙ₋₂ → ...
Merge alternating:
Take from first: L₀
Take from second: Lₙ
Take from first: L₁
Take from second: Lₙ₋₁
...
By reversing the second half first:
We get nodes in correct order for merging! ✓
🎯 Approach 1: Using Array/List (Extra Space)
🌟 ELI5: The Simple Way First!
Think of it like shuffling cards:
You have cards in order: [1, 2, 3, 4, 5, 6]
You want: [1, 6, 2, 5, 3, 4]
Pattern: First, Last, Second, Second-Last, Third, Third-Last
How to do it?
1. Spread all cards on a table (put in array)
2. Use two hands:
- Left hand points to first card
- Right hand points to last card
3. Pick alternately: left, right, left, right...
4. Connect them in this order!
The Most Natural Thinking 💭
Core Logic:
Step 1: Store all nodes in an array (like spreading cards)
Step 2: Use two pointers (left hand, right hand)
Step 3: Relink nodes alternating from both ends
Step-by-Step Code Walkthrough
/**
* Using array to store nodes
* Time: O(n), Space: O(n)
*/
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return; // Empty or single node, nothing to reorder
}
// STEP 1: Store all nodes in an array
List<ListNode> nodes = new ArrayList<>();
ListNode current = head;
while (current != null) {
nodes.add(current); // Add each node to array
current = current.next;
}
// Now nodes array has: [node1, node2, node3, node4, ...]
// We can access any node by index!
// STEP 2: Use two pointers to reorder
int left = 0; // Points to start
int right = nodes.size() - 1; // Points to end
// STEP 3: Connect alternately
while (left < right) {
// Connect: left -> right
nodes.get(left).next = nodes.get(right);
left++; // Move left pointer forward
// Check if we're done
if (left == right) break;
// Connect: right -> (new left position)
nodes.get(right).next = nodes.get(left);
right--; // Move right pointer backward
}
// STEP 4: Close the list (very important!)
nodes.get(left).next = null;
}
🔍 Super Detailed Dry Run
Example: [1,2,3,4,5]
Original list: 1 -> 2 -> 3 -> 4 -> 5 -> null
═══════════════════════════════════════════════════════════════
STEP 1: Store in Array
═══════════════════════════════════════════════════════════════
nodes = [node1, node2, node3, node4, node5]
index0 index1 index2 index3 index4
Think of it as:
nodes[0] = the actual node with value 1
nodes[1] = the actual node with value 2
nodes[2] = the actual node with value 3
nodes[3] = the actual node with value 4
nodes[4] = the actual node with value 5
═══════════════════════════════════════════════════════════════
STEP 2: Initialize Pointers
═══════════════════════════════════════════════════════════════
left = 0 (pointing to node with value 1)
right = 4 (pointing to node with value 5)
Visual:
[node1, node2, node3, node4, node5]
↑ ↑
left right
═══════════════════════════════════════════════════════════════
ITERATION 1:
═══════════════════════════════════════════════════════════════
Action: Connect left -> right
nodes.get(0).next = nodes.get(4)
This means: 1.next = 5
Now: 1 -> 5
Move left forward: left = 1
Check: left == right? (1 == 4? No)
Action: Connect right -> left
nodes.get(4).next = nodes.get(1)
This means: 5.next = 2
Now: 1 -> 5 -> 2
Move right backward: right = 3
Current state: 1 -> 5 -> 2
Pointers now:
[node1, node2, node3, node4, node5]
↑ ↑
left right
═══════════════════════════════════════════════════════════════
ITERATION 2:
═══════════════════════════════════════════════════════════════
Action: Connect left -> right
nodes.get(1).next = nodes.get(3)
This means: 2.next = 4
Now: 1 -> 5 -> 2 -> 4
Move left forward: left = 2
Check: left == right? (2 == 3? No)
Action: Connect right -> left
nodes.get(3).next = nodes.get(2)
This means: 4.next = 3
Now: 1 -> 5 -> 2 -> 4 -> 3
Move right backward: right = 2
Pointers now:
[node1, node2, node3, node4, node5]
↑
left & right (same!)
═══════════════════════════════════════════════════════════════
ITERATION 3:
═══════════════════════════════════════════════════════════════
Check: left < right? (2 < 2? No!)
Exit while loop!
═══════════════════════════════════════════════════════════════
STEP 4: Close the list
═══════════════════════════════════════════════════════════════
Action: Set last node's next to null
nodes.get(2).next = null
This means: 3.next = null
Final result: 1 -> 5 -> 2 -> 4 -> 3 -> null ✓
🎨 Visual Animation
Initial Array:
Index: 0 1 2 3 4
Value: [1] [2] [3] [4] [5]
↑ ↑
left right
Step 1: Connect 1 -> 5
1 -> 5
Step 2: Connect 5 -> 2, move pointers
1 -> 5 -> 2
↑ ↑
left right
Step 3: Connect 2 -> 4
1 -> 5 -> 2 -> 4
Step 4: Connect 4 -> 3, move pointers
1 -> 5 -> 2 -> 4 -> 3
↑
left & right
Step 5: Close with null
1 -> 5 -> 2 -> 4 -> 3 -> null ✓
💡 Why This Works
The Key Insight:
By storing in array, we get RANDOM ACCESS!
- Can access first node: nodes[0]
- Can access last node: nodes[n-1]
- Can access any node instantly!
Without array:
- To get last node: must traverse entire list ✗
With array:
- To get last node: nodes[size-1] ✓
This makes alternating easy!
Why Set Last Node to Null?
Important: Without this, list has a cycle!
After relinking: 1 -> 5 -> 2 -> 4 -> 3
↓
still points to old next!
If we don't set 3.next = null:
3 might still point to 4 (from original list)
This creates a cycle! ✗
Setting 3.next = null:
1 -> 5 -> 2 -> 4 -> 3 -> null ✓
⏰ Time: O(n) - One pass to store, one pass to relink
💾 Space: O(n) - Array stores all nodes
✓ Simple and clear, but uses extra space!
🎯 Approach 2: Three-Step In-Place (Optimal) ⭐
🌟 ELI5: The Magic Trick Way!
Think of it like rearranging a deck of cards WITHOUT a table:
You have cards: [1, 2, 3, 4, 5, 6]
You want: [1, 6, 2, 5, 3, 4]
Without a table (no extra space), how?
Magic Trick in 3 steps:
1. Find middle card (3/4 boundary)
2. Flip the second half upside down [6, 5, 4]
3. Shuffle them together: 1, 6, 2, 5, 3, 4
That's it! ✨
Better Approach 💡
🧠 The Core Insight
Three steps, all in-place:
1. Find middle (fast & slow pointers)
2. Reverse second half (flip cards)
3. Merge alternating (shuffle together)
No extra space needed! ✓
🎯 STEP-BY-STEP BREAKDOWN
Let me explain each step in extreme detail:
📍 STEP 1: Find the Middle
What we're doing: Split the list into two halves
How: Fast & slow pointers (you already know this!)
// Fast moves 2 steps, slow moves 1 step
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // Slow: 1 step
fast = fast.next.next; // Fast: 2 steps
}
Why this works:
When fast reaches end:
Fast traveled: n steps
Slow traveled: n/2 steps
Slow is at MIDDLE! ✓
Example: [1, 2, 3, 4, 5, 6] - EVEN length
Initial: slow = 1, fast = 1
Step 1: slow = 2, fast = 3
Step 2: slow = 3, fast = 5
Step 3: slow = 4, fast = null (exit!)
slow ends at 4 ✓
Split:
First half: 1 -> 2 -> 3 -> 4
Second half: 5 -> 6 (starting from slow.next)
After Step 1:
ListNode second = slow.next; // Start of second half
slow.next = null; // Cut the connection!
Now we have:
first: 1 -> 2 -> 3 -> 4 -> null
second: 5 -> 6 -> null
🔄 STEP 2: Reverse Second Half
What we're doing: Flip the second half backwards
Before: 4 -> 5 -> 6 -> null
After: 6 -> 5 -> 4 -> null
The Reversal Algorithm (Detailed!):
private ListNode reverseList(ListNode head) {
ListNode prev = null; // Previous node (starts as null)
ListNode current = head; // Current node we're processing
while (current != null) {
// Save the next node (we'll need it!)
ListNode next = current.next;
// REVERSE: Point current backwards to prev
current.next = prev;
// Move both pointers forward
prev = current;
current = next;
}
return prev; // prev is now the new head!
}
Let me trace this SUPER slowly with [4, 5, 6]:
Initial State:
prev = null
current = 4
List: 4 -> 5 -> 6 -> null
═══════════════════════════════════════════════════════════════
ITERATION 1: Process node 4
═══════════════════════════════════════════════════════════════
Step 1: Save next
next = current.next = 5
(We save 5 so we don't lose the rest of the list!)
Step 2: Reverse the pointer
current.next = prev
4.next = null
Now 4 points to null: 4 -> null
Step 3: Move pointers forward
prev = current = 4
current = next = 5
Current state:
prev: 4 -> null
current: 5 -> 6 -> null
(We've detached 4 and flipped it!)
═══════════════════════════════════════════════════════════════
ITERATION 2: Process node 5
═══════════════════════════════════════════════════════════════
Step 1: Save next
next = current.next = 6
Step 2: Reverse the pointer
current.next = prev
5.next = 4
Now: 5 -> 4 -> null
Step 3: Move pointers forward
prev = current = 5
current = next = 6
Current state:
prev: 5 -> 4 -> null
current: 6 -> null
(We've attached 5 to the reversed chain!)
═══════════════════════════════════════════════════════════════
ITERATION 3: Process node 6
═══════════════════════════════════════════════════════════════
Step 1: Save next
next = current.next = null
Step 2: Reverse the pointer
current.next = prev
6.next = 5
Now: 6 -> 5 -> 4 -> null
Step 3: Move pointers forward
prev = current = 6
current = next = null
Current state:
prev: 6 -> 5 -> 4 -> null
current: null
(Loop will exit!)
═══════════════════════════════════════════════════════════════
DONE! Return prev
═══════════════════════════════════════════════════════════════
Return prev = 6
Result: 6 -> 5 -> 4 -> null ✓
Visual Summary of Reversal:
Before: 4 -> 5 -> 6 -> null
Process 4: null <- 4 5 -> 6 -> null
Process 5: null <- 4 <- 5 6 -> null
Process 6: null <- 4 <- 5 <- 6
After: 6 -> 5 -> 4 -> null ✓
🔀 STEP 3: Merge Alternately
What we're doing: Shuffle both halves together
We have:
first: 1 -> 2 -> 3 -> null
second: 6 -> 5 -> 4 -> null
Want:
1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null
The Merge Algorithm (Super Detailed!):
private void mergeLists(ListNode first, ListNode second) {
while (second != null) {
// CRITICAL: Save next nodes BEFORE modifying!
ListNode firstNext = first.next;
ListNode secondNext = second.next;
// Connect: first -> second
first.next = second;
// Connect: second -> firstNext
second.next = firstNext;
// Move to next pair
first = firstNext;
second = secondNext;
}
}
Let me trace this SUPER slowly:
Initial State:
first: 1 -> 2 -> 3 -> 4 -> null
second: 6 -> 5 -> null (after reversing 5 -> 6)
═══════════════════════════════════════════════════════════════
ITERATION 1: Connect 1 and 6
═══════════════════════════════════════════════════════════════
Step 1: Save next nodes (IMPORTANT!)
firstNext = first.next = 2
secondNext = second.next = 5
Why save? Because we're about to change the .next pointers!
If we don't save, we lose track of 2 and 5!
Step 2: Connect first -> second
first.next = second
1.next = 6
Now: 1 -> 6
Step 3: Connect second -> firstNext
second.next = firstNext
6.next = 2
Now: 1 -> 6 -> 2
Step 4: Move to next pair
first = firstNext = 2
second = secondNext = 5
Current state:
Connected so far: 1 -> 6 -> 2
Remaining to connect:
first: 2 -> 3 -> 4 -> null
second: 5 -> null
═══════════════════════════════════════════════════════════════
ITERATION 2: Connect 2 and 5
═══════════════════════════════════════════════════════════════
Step 1: Save next nodes
firstNext = first.next = 3
secondNext = second.next = null
Step 2: Connect first -> second
first.next = second
2.next = 5
Now: 1 -> 6 -> 2 -> 5
Step 3: Connect second -> firstNext
second.next = firstNext
5.next = 3
Now: 1 -> 6 -> 2 -> 5 -> 3
Step 4: Move to next pair
first = firstNext = 3
second = secondNext = null
Current state:
Connected so far: 1 -> 6 -> 2 -> 5 -> 3
Remaining:
first: 3 -> 4 -> null
second: null
═══════════════════════════════════════════════════════════════
DONE! second is null, exit loop
═══════════════════════════════════════════════════════════════
The remaining first nodes (3 -> 4) are already connected!
Final result: 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null ✓
Visual Summary of Merge:
Start:
first: 1 -> 2 -> 3 -> 4
second: 6 -> 5 (reversed from 5 -> 6)
After iteration 1:
1 -> 6 -> 2 -> 3 -> 4
↓
5
After iteration 2:
1 -> 6 -> 2 -> 5 -> 3 -> 4
(already connected)
Done! second is null, exit
1 -> 6 -> 2 -> 5 -> 3 -> 4 ✓
🎯 Putting It All Together
Complete Implementation with Comments:
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return; // Nothing to reorder
}
// ═══════════════════════════════════════════════════════
// STEP 1: Find middle and split
// ═══════════════════════════════════════════════════════
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Split into two halves
ListNode second = slow.next; // Second half starts here
slow.next = null; // Cut first half
// Now we have:
// first half: head -> ... -> slow -> null
// second half: second -> ... -> null
// ═══════════════════════════════════════════════════════
// STEP 2: Reverse second half
// ═══════════════════════════════════════════════════════
second = reverseList(second);
// Now second half is reversed!
// first half: head -> ... -> slow -> null
// second half: last -> ... -> second -> null
// ═══════════════════════════════════════════════════════
// STEP 3: Merge alternately
// ═══════════════════════════════════════════════════════
ListNode first = head;
mergeLists(first, second);
// Done! List is now reordered in-place!
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next; // Save next
current.next = prev; // Reverse
prev = current; // Move prev
current = next; // Move current
}
return prev; // New head
}
private void mergeLists(ListNode first, ListNode second) {
while (second != null) {
// Save next nodes (critical!)
ListNode firstNext = first.next;
ListNode secondNext = second.next;
// Connect first -> second -> firstNext
first.next = second;
second.next = firstNext;
// Move to next pair
first = firstNext;
second = secondNext;
}
}
⏰ Time: O(n) - Three O(n) operations
💾 Space: O(1) - Only pointers, no extra space!
🔍 Dry Run
Example 1: [1,2,3,4,5]
Goal: Reorder to [1,5,2,4,3]
STEP 1: Find Middle & Split
Initial:
slow = 1, fast = 1
Iteration 1:
slow = 2, fast = 3
Iteration 2:
slow = 3, fast = 5
Check: fast.next != null? No! (5.next = null)
Loop ends
slow is at node 3 (index 2) ✓
Split:
second = slow.next = 4
slow.next = null (cut first half)
Result:
first: 1 -> 2 -> 3 -> null
second: 4 -> 5 -> null
STEP 2: Reverse Second Half
Call reverseList(4 -> 5):
Initial: prev = null, current = 4
Iteration 1:
next = 5
4.next = null
prev = 4, current = 5
Iteration 2:
next = null
5.next = 4
prev = 5, current = null
Return prev = 5
Result:
first: 1 -> 2 -> 3 -> null
second: 5 -> 4 -> null (reversed!)
STEP 3: Merge Lists
Call mergeLists(first=1, second=5):
Iteration 1:
firstNext = 2
secondNext = 4
1.next = 5
5.next = 2
first = 2, second = 4
Current state: 1 -> 5 -> 2 -> 3 -> null
4 -> null
Iteration 2:
firstNext = 3
secondNext = null
2.next = 4
4.next = 3
first = 3, second = null
Current state: 1 -> 5 -> 2 -> 4 -> 3 -> null
second = null, loop ends
Final: 1 -> 5 -> 2 -> 4 -> 3 -> null ✓
Example 2: [1,2,3,4]
Goal: Reorder to [1,4,2,3]
STEP 1: Find Middle & Split
Fast & slow:
Initial: slow = 1, fast = 1
Step 1: slow = 2, fast = 3
Step 2: slow = 3, fast = null (4.next = null)
Split:
second = 3.next = 4
3.next = null
Result:
first: 1 -> 2 -> null
second: 3 -> 4 -> null
STEP 2: Reverse Second Half
Reverse 3 -> 4:
Result: 4 -> 3 -> null
Now:
first: 1 -> 2 -> null
second: 4 -> 3 -> null
STEP 3: Merge
Iteration 1:
1.next = 4
4.next = 2
first = 2, second = 3
Iteration 2:
2.next = 3
3.next = null
first = null, second = null
Final: 1 -> 4 -> 2 -> 3 -> null ✓
🎯 Why This Works - Deep Dive
The Three-Step Strategy Breakdown:
═══════════════════════════════════════════════════════════════
Step 1: Find Middle
Purpose: Split list into two halves
Method: Fast & slow pointers
Result: Two separate lists
For odd length (5 nodes):
First half: 3 nodes (1,2,3)
Second half: 2 nodes (4,5)
For even length (4 nodes):
First half: 2 nodes (1,2)
Second half: 2 nodes (3,4)
Step 2: Reverse Second Half
Purpose: Get nodes in correct order for merging
Method: In-place reversal
Result: Second half reversed
Before: 4 -> 5 -> null
After: 5 -> 4 -> null
Why reverse?
Original order: first, last
Need: last, second-last
Reversal achieves this!
Step 3: Merge Alternately
Purpose: Interleave nodes from both halves
Method: Take one from first, one from second
Result: Final reordered list
Pattern:
first[0] -> second[0] -> first[1] -> second[1] -> ...
Visual:
first: 1 -> 2 -> 3
second: 6 -> 5 -> 4
Merge:
1 -> 6 (from first, then second)
2 -> 5 (from first, then second)
3 -> 4 (from first, then second)
Result: 1 -> 6 -> 2 -> 5 -> 3 -> 4
Why First Half Can Be One Longer:
═══════════════════════════════════════════════════════════════
For odd length list:
[1, 2, 3, 4, 5]
Split at middle:
first: [1, 2, 3]
second: [4, 5]
Merge:
1 -> 5 -> 2 -> 4 -> 3
Middle element (3) ends up last ✓
This is correct! First half being longer
doesn't affect the pattern because we merge
until second is exhausted, and any remaining
from first (just the middle) stays at end.
The Reversal Insight:
═══════════════════════════════════════════════════════════════
Original list: [1, 2, 3, 4, 5, 6]
What we want:
1 -> 6 -> 2 -> 5 -> 3 -> 4
If we just split without reversing:
first: 1 -> 2 -> 3
second: 4 -> 5 -> 6
Merge: 1 -> 4 -> 2 -> 5 -> 3 -> 6
Wrong! We get 4 instead of 6!
With reversal:
first: 1 -> 2 -> 3
second: 6 -> 5 -> 4 (reversed!)
Merge: 1 -> 6 -> 2 -> 5 -> 3 -> 4
Correct! ✓
Time Complexity:
═══════════════════════════════════════════════════════════════
Step 1: Find Middle
Fast & slow traverse entire list
Time: O(n)
Step 2: Reverse Second Half
Reverse n/2 nodes
Time: O(n/2) = O(n)
Step 3: Merge
Merge n/2 pairs
Time: O(n/2) = O(n)
Total: O(n) + O(n) + O(n) = O(n) ✓
Space: O(1) - Only pointers, no extra data structures
Why In-Place?
═══════════════════════════════════════════════════════════════
All operations modify pointers only:
- Finding middle: just traversal
- Reversing: changes .next pointers
- Merging: reconnects .next pointers
No new nodes created!
No arrays or lists used!
Space: O(1) ✓
Edge Cases Handling
Case 1: Empty list
if (head == null) return;
Handled at start ✓
Case 2: Single node
if (head.next == null) return;
Handled at start ✓
Case 3: Two nodes [1, 2]
Step 1: slow = 2, split into [1] and [2]
Step 2: Reverse [2] -> [2]
Step 3: Merge 1 -> 2
Result: 1 -> 2 ✓
Case 4: Three nodes [1, 2, 3]
Step 1: slow = 2, split into [1, 2] and [3]
Step 2: Reverse [3] -> [3]
Step 3: Merge 1 -> 3 -> 2
Result: 1 -> 3 -> 2 ✓
Case 5: Odd length [1, 2, 3, 4, 5]
First half one longer
Middle element ends up last
Correct! ✓
Case 6: Even length [1, 2, 3, 4]
Both halves equal
Perfect alternation
Correct! ✓
⚠️ Common Mistakes to Avoid
Mistake 1: Not cutting first half
// ❌ WRONG - Lists still connected
ListNode second = slow.next;
// slow.next still points to second!
// ✓ CORRECT - Cut the connection
ListNode second = slow.next;
slow.next = null; // Cut first half
Mistake 2: Wrong split point
// ❌ WRONG - slow starts at head.next
ListNode slow = head.next;
ListNode fast = head;
// Results in wrong middle!
// ✓ CORRECT - Both start at head
ListNode slow = head;
ListNode fast = head;
Mistake 3: Not saving next nodes in merge
// ❌ WRONG - Loses references
while (second != null) {
first.next = second;
second.next = first.next; // Wrong! first.next is now second!
}
// ✓ CORRECT - Save next nodes first
while (second != null) {
ListNode firstNext = first.next;
ListNode secondNext = second.next;
first.next = second;
second.next = firstNext;
first = firstNext;
second = secondNext;
}
Mistake 4: Wrong merge order
// ❌ WRONG - Connects second before first
second.next = first;
first.next = second.next;
// Wrong pattern!
// ✓ CORRECT - first -> second -> firstNext
first.next = second;
second.next = firstNext;
Mistake 5: Not handling null in merge
// ❌ WRONG - Might access null.next
while (first != null && second != null) {
first.next = second;
first = first.next; // Could be null!
}
// ✓ CORRECT - Check second only
while (second != null) {
// first is always valid when second exists
}
🎯 Pattern Recognition
Problem Type: Reorder Linked List
Core Pattern: Three-Step Algorithm (Find, Reverse, Merge)
When to Apply:
✓ Reorder from both ends
✓ Alternate pattern needed
✓ In-place requirement
✓ Combine start and end elements
✓ Linked list manipulation
Recognition Keywords:
- "Reorder list"
- "L₀ → Lₙ → L₁ → Lₙ₋₁"
- "First and last alternating"
- "In-place" or "constant space"
- "Rearrange nodes"
Similar Problems:
- Reverse Linked List (LC 206) - Step 2 component
- Middle of Linked List (LC 876) - Step 1 component
- Merge Two Sorted Lists (LC 21) - Step 3 similar
- Palindrome Linked List (LC 234) - Uses similar steps
Key Components:
┌────────────────────────────────────────────┐
│ Step 1: Find middle (fast & slow) │
│ Step 2: Reverse second half │
│ Step 3: Merge alternately │
│ Time: O(n), Space: O(1) │
└────────────────────────────────────────────┘
This combines multiple classic techniques!
🧠 Interview Strategy
Step 1: "Three-step approach: find middle, reverse, merge"
Step 2: "Fast & slow to find middle and split"
Step 3: "Reverse second half in-place"
Step 4: "Merge alternating from both halves"
Step 5: "All in-place, O(n) time, O(1) space"
Key Points to Mention:
- Three distinct steps
- Find middle using fast & slow pointers
- Split list into two halves
- Reverse second half (crucial step!)
- Merge alternately: first->second->first->second
- All operations in-place
- Time: O(n) for each step = O(n) total
- Space: O(1) - only pointers
- Alternative: Array O(n) space
Why This Approach?
"I'll use a three-step approach. First, I find the middle using
fast and slow pointers and split the list into two halves.
Second, I reverse the second half to get nodes in the order I
need for merging. Third, I merge the two halves alternately -
taking one node from the first half, then one from the reversed
second half. This gives me the required reordering pattern.
All steps are in-place, giving O(n) time and O(1) space."
Why Reverse Second Half?
"Reversing the second half is key. After splitting at the
middle, if I want to alternate between first and last elements,
I need the second half in reverse order. This way, when I merge,
I naturally get the pattern: first[0] -> last -> first[1] ->
second-last, etc."
Edge Cases to Mention:
✓ Empty list (return immediately)
✓ Single node (return immediately)
✓ Two nodes (simple merge)
✓ Odd length (first half one longer)
✓ Even length (equal halves)
📝 Quick Revision Notes
🎯 Core Concept:
Reorder List: Use 3-step algorithm! Step 1: Find middle (fast & slow), split. Step 2: Reverse second half. Step 3: Merge alternately (first->second->first->second). Pattern: L₀→Lₙ→L₁→Lₙ₋₁. All in-place! O(n) time, O(1) space!
⚡ Quick Implementation:
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 Test {
public ListNode reorderList(ListNode head) {
if(head == null) {
return head;
}
// // Approach 1 - using arraylist
// ArrayList<ListNode> list = new ArrayList<>();
// // Add to list
// ListNode curr = head;
// while (curr != null) {
// list.add(curr);
// curr = curr.next;
// }
// // Add one from left and one from right. Break once both meet.
// int left = 0;
// int right = list.size() - 1;
// // Example: 1, 2, 3, 4, 5
// while (left < right) {
// // 1st iteration: left = 0 and right = 4
// // 2nd iteration: left = 1 and right = 3
// list.get(left).next = list.get(right); // forms 1 -> 5
// left++; // 2 (index 1)
// // consider a 2 node list. If left and right are same, we need to break.
// // else goes to a wrong step next.
// if(left == right) {
// break;
// }
// list.get(right).next = list.get(left); // forms 1 -> 5 -> 2
// right--; // 4 (index 3)
// }
// // Set last node's next to null. Else infinite loop.
// // Without this, 3 would be still pointing to 4 which further points to 3 and so on like an infinite loop.
// list.get(left).next = null;
// return head;
// Approach 2: 4 step process.
// Examples: [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5, 6]
// in case of [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5, 6], slow becomes 3 and 4.
// odd length: [1,2,3,4,5] => [1,2,3] and [4,5] => [1,2,3] and [5,4] => [1,5,2,4,3]
// even length: [1,2,3,4,5,6] => [1,2,3,4] and [5,6] => [1,2,3,4] and [6,5] => [1,6,2,5,3,4]
// Step 1: Get middle node.
ListNode middleNode = getMiddleNode(head);
// Step 2: Cut into 2 halves.
ListNode firstHalf = head;
ListNode secondHalf = middleNode.next;
middleNode.next = null; // actual cut
// Step 3: reverse the 2nd half.
secondHalf = reverse(secondHalf);
// Step 4: Merge both lists.
merge(firstHalf, secondHalf);
return head;
}
private void merge(ListNode first, ListNode second) {
while (second != null) {
// Save the next nodes before breaking the link.
ListNode nextFirst = first.next;
ListNode nextSecond = second.next;
first.next = second;
second.next = nextFirst;
first = nextFirst;
second = nextSecond;
}
}
private ListNode reverse(ListNode head) {
// 1 -> 2 -> 3 ===> null <- 1 <- 2 <- 3
ListNode curr = head;
ListNode prev = null;
while (curr != null) {
// Save the next node before updating links
ListNode next = curr.next;
// Point curr next to prev (reverse the link)
curr.next = prev;
// Update prev and curr pointers
prev = curr;
curr = next;
}
return prev; // because curr will be null and we break from loop.
}
private ListNode getMiddleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// in case of [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5, 6], slow becomes 3 and 4.
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " -> ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Test t = new Test();
ListNode head1 = new ListNode(1); // 1, 2, 3, 4, 5
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(4);
head1.next.next.next.next = new ListNode(5);
// t.reorderList(head1);
t.printList(t.reorderList(head1)); // 1,5,2,4,3
t.printList(t.reorderList(null)); // empty list
t.printList(new ListNode(1)); // single element
ListNode head2 = new ListNode(1); // 2 elements
head2.next = new ListNode(2);
t.printList(t.reorderList(head2));
ListNode head3 = new ListNode(1); // 3 elements
head3.next = new ListNode(2);
head3.next.next = new ListNode(3);
t.printList(t.reorderList(head3));
ListNode head4 = new ListNode(1);
head4.next = new ListNode(2);
head4.next.next = new ListNode(3);
head4.next.next.next = new ListNode(4);
head4.next.next.next.next = new ListNode(5);
head4.next.next.next.next.next = new ListNode(6); // 1,6,2,5,3,4
t.printList(t.reorderList(head4));
}
}
🔑 Key Insights:
- Pattern: Three-Step Algorithm
- Step 1: Find middle (fast & slow)
- Step 2: Reverse second half (critical!)
- Step 3: Merge alternately
- Why Reverse: Gets nodes in correct order for merging
- Split: slow.next = null (cut connection!)
- Merge: first->second->firstNext, repeat
- Save Next: Store next nodes before relinking
- Time: O(n), Space: O(1)
🎪 Memory Aid:
"Find middle, reverse second, merge alternately!"
Think: "Three steps: Split, Flip, Zip!" 🎯
💡 The Key Insight:
Why reverse second half?
Want: 1 -> 6 -> 2 -> 5 -> 3 -> 4
Split: [1,2,3] and [4,5,6]
Without reverse: 1->4, 2->5, 3->6 ✗
With reverse: [1,2,3] and [6,5,4]
Merge: 1->6, 2->5, 3->4 ✓
⚠️ Critical Details:
1. Step 1: Fast & slow to find middle
2. Split: second = slow.next, slow.next = null
3. Cut connection! (slow.next = null)
4. Step 2: Reverse second half
5. Use standard reverse algorithm
6. Step 3: Merge while (second != null)
7. Save next: tmp1 = first.next, tmp2 = second.next
8. Link: first->second->tmp1
9. Move: first = tmp1, second = tmp2
🔥 The Three Steps:
Original: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Step 1: Split at middle
[1 -> 2 -> 3] [4 -> 5 -> 6]
Step 2: Reverse second
[1 -> 2 -> 3] [6 -> 5 -> 4]
Step 3: Merge alternately
1 -> 6 -> 2 -> 5 -> 3 -> 4 ✓
💡 Why Each Step Matters:
Step 1 (Find Middle):
Splits problem into two halves
Makes reversal and merging manageable
Step 2 (Reverse):
Gets second half in correct order
Last becomes first, second-last becomes second
Essential for alternating pattern!
Step 3 (Merge):
Combines both halves
Alternates: first, second, first, second
Creates final pattern
🧪 Edge Cases
Case 1: Empty list
Input: head = null
Output: null
(Handled by initial check)
Case 2: Single node
Input: head = [1]
Output: [1]
(Handled by initial check)
Case 3: Two nodes
Input: head = [1,2]
Output: [1,2]
(Split into [1] and [2], merge back)
Case 4: Three nodes
Input: head = [1,2,3]
Output: [1,3,2]
(First half longer, middle ends up last)
Case 5: Odd length
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
(First half: 3, Second half: 2)
Case 6: Even length
Input: head = [1,2,3,4]
Output: [1,4,2,3]
(Equal halves)
All handled correctly! ✓
Related Patterns
- Reverse Linked List (LC 206) - Used in Step 2
- Middle of Linked List (LC 876) - Used in Step 1
- Palindrome Linked List (LC 234) - Similar technique
- Merge Two Lists (LC 21) - Similar to Step 3
Happy practicing! 🎯
Note: This is a FANTASTIC problem that tests your ability to combine multiple techniques! It's frequently asked in FAANG interviews because it shows mastery of linked list manipulation! Master the three steps and you'll ace it! 🚀