100. Reverse Nodes in k-Group
🔗 LeetCode Problem: 25. Reverse Nodes in k-Group
📊 Difficulty: Hard
🏷️ Topics: Linked List, Recursion
Problem Statement
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
You may not alter the values in the list's nodes, only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Visual:
Original: 1 → 2 → 3 → 4 → 5 → null
└─┬─┘ └─┬─┘ │
grp1 grp2 left
After: 2 → 1 → 4 → 3 → 5 → null
└─┬─┘ └─┬─┘ │
reversed reversed same
Example 2:
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Visual:
Original: 1 → 2 → 3 → 4 → 5 → null
└───┬───┘ └─┬─┘
grp1 leftover
After: 3 → 2 → 1 → 4 → 5 → null
└───┬───┘ └─┬─┘
reversed same
Constraints:
- The number of nodes in the list is n.
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1) extra memory (i.e., not counting the recursion stack)?
🌟 ELI5: The Simple Idea!
Think of reversing segments of a chain:
Original chain: [1, 2, 3, 4, 5]
k = 2 (reverse in groups of 2)
Step 1: Mark groups
[1, 2] [3, 4] [5]
↑ ↑ ↑
grp1 grp2 leftover
Step 2: Reverse each complete group
[2, 1] [4, 3] [5]
↑ ↑ ↑
reversed reversed unchanged
Step 3: Connect groups
2 → 1 → 4 → 3 → 5 ✓
Key insight: Only reverse COMPLETE groups!
The Challenge:
Normal reverse: Easy (LC 206)
1 → 2 → 3 → null
3 → 2 → 1 → null
k-group reverse: Complex!
- Must find group boundaries
- Reverse each group separately
- Reconnect groups
- Leave incomplete group unchanged
🎨 Visual Understanding
The Reversal Process
Input: [1,2,3,4,5], k = 3
═══════════════════════════════════════════════════════════════
Step 1: Identify Groups
═══════════════════════════════════════════════════════════════
Original: 1 → 2 → 3 → 4 → 5 → null
Group 1: [1, 2, 3] ✓ (complete, k=3)
Leftover: [4, 5] ✗ (incomplete, only 2 nodes)
═══════════════════════════════════════════════════════════════
Step 2: Reverse Group 1
═══════════════════════════════════════════════════════════════
Before: 1 → 2 → 3 → 4 → 5
└───┬───┘
reverse this
During reversal:
null ← 1 ← 2 ← 3 4 → 5
│ ↑
tail next group
After: 3 → 2 → 1 → 4 → 5
↑ ↑ ↑
new old rest
head head
═══════════════════════════════════════════════════════════════
Step 3: Keep Leftover As Is
═══════════════════════════════════════════════════════════════
[4, 5] has only 2 nodes < k=3
Leave unchanged
Final: 3 → 2 → 1 → 4 → 5 → null ✓
🎯 Approach 1: Iterative ⭐
The Standard Solution
Algorithm:
1. Use dummy node for easier head handling
2. For each group:
a. Check if k nodes exist
b. If yes: reverse the k nodes
c. If no: stop (leave rest unchanged)
d. Reconnect reversed group
3. Move to next group
Implementation
/**
* Iterative approach with group reversal
* Time: O(n), Space: O(1)
*/
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prevGroupEnd = dummy;
while (true) {
// Check if k nodes exist
ListNode kthNode = getKthNode(prevGroupEnd, k);
if (kthNode == null) {
break; // Less than k nodes left
}
// Save next group start
ListNode nextGroupStart = kthNode.next;
// Reverse current group
ListNode groupStart = prevGroupEnd.next;
ListNode prev = nextGroupStart;
ListNode curr = groupStart;
// Reverse k nodes
while (curr != nextGroupStart) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// Reconnect
prevGroupEnd.next = kthNode; // Point to new head of reversed group
prevGroupEnd = groupStart; // Old head is now tail
}
return dummy.next;
}
// Get the k-th node from start (1-indexed)
private ListNode getKthNode(ListNode start, int k) {
ListNode curr = start;
while (curr != null && k > 0) {
curr = curr.next;
k--;
}
return curr;
}
⏰ Time: O(n) - Each node visited twice (once for checking, once for reversing)
💾 Space: O(1) - Only pointers
🔍 Super Detailed Dry Run
Example: head = [1,2,3,4,5], k = 2
Goal: Reverse in groups of 2 → [2,1,4,3,5]
Initial:
dummy → 1 → 2 → 3 → 4 → 5 → null
↑
prevGroupEnd
═══════════════════════════════════════════════════════════════
Iteration 1: Process First Group [1, 2]
═══════════════════════════════════════════════════════════════
Check if k nodes exist:
kthNode = getKthNode(dummy, 2)
Start at dummy, move 2 times
dummy → 1 → 2
1 2
kthNode = 2 ✓ (exists)
Save pointers:
nextGroupStart = kthNode.next = 3
groupStart = prevGroupEnd.next = 1
dummy → 1 → 2 → 3 → 4 → 5
↑ ↑ ↑
group kth next
Start group
Reverse group [1, 2]:
prev = nextGroupStart = 3
curr = groupStart = 1
Reverse iteration 1:
next = 2
1.next = 3 (point to prev)
prev = 1, curr = 2
3 ← 1 2 → 3 → 4 → 5
Reverse iteration 2:
next = 3
2.next = 1 (point to prev)
prev = 2, curr = 3
3 ← 1 ← 2 3 → 4 → 5
Loop exits (curr == nextGroupStart)
After reversal:
Reversed chain: 2 → 1 → 3
Reconnect:
prevGroupEnd.next = kthNode (2)
dummy → 2 → 1 → 3 → 4 → 5
prevGroupEnd = groupStart (1)
State:
dummy → 2 → 1 → 3 → 4 → 5 → null
↑
prevGroupEnd
═══════════════════════════════════════════════════════════════
Iteration 2: Process Second Group [3, 4]
═══════════════════════════════════════════════════════════════
Check if k nodes exist:
kthNode = getKthNode(1, 2)
Start at 1, move 2 times
1 → 3 → 4
1 2
kthNode = 4 ✓ (exists)
Save pointers:
nextGroupStart = 5
groupStart = 3
Reverse group [3, 4]:
prev = 5
curr = 3
Reverse iteration 1:
3.next = 5
prev = 3, curr = 4
Reverse iteration 2:
4.next = 3
prev = 4, curr = 5
Reversed: 5 ← 3 ← 4
Reconnect:
prevGroupEnd.next = 4
dummy → 2 → 1 → 4 → 3 → 5
prevGroupEnd = 3
State:
dummy → 2 → 1 → 4 → 3 → 5 → null
↑
prevGroupEnd
═══════════════════════════════════════════════════════════════
Iteration 3: Check for Next Group
═══════════════════════════════════════════════════════════════
Check if k nodes exist:
kthNode = getKthNode(3, 2)
Start at 3, move 2 times
3 → 5 → null
1 (only 1 node available)
kthNode = null ✗
Break loop (less than k nodes left)
═══════════════════════════════════════════════════════════════
Return Result
═══════════════════════════════════════════════════════════════
Return dummy.next
Final: 2 → 1 → 4 → 3 → 5 → null ✓
Result: [2, 1, 4, 3, 5]
🎯 Approach 2: Recursive ⭐
The Elegant Solution
Algorithm:
Base case: Less than k nodes → return head
Recursive case:
1. Reverse first k nodes
2. Recursively reverse rest
3. Connect reversed part to recursed result
Implementation
/**
* Recursive approach
* Time: O(n), Space: O(n/k) - recursion stack
*/
public ListNode reverseKGroup(ListNode head, int k) {
// Check if k nodes exist
ListNode curr = head;
int count = 0;
while (curr != null && count < k) {
curr = curr.next;
count++;
}
// Less than k nodes, return as is
if (count < k) {
return head;
}
// Reverse first k nodes
ListNode prev = null;
curr = head;
for (int i = 0; i < k; i++) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// Recursively reverse rest
// 'head' is now tail of reversed group
head.next = reverseKGroup(curr, k);
// Return new head (prev)
return prev;
}
⏰ Time: O(n)
💾 Space: O(n/k) - Recursion depth
Visual Recursion
reverseKGroup([1,2,3,4,5], 2)
↓
Reverse [1,2]
2 → 1 → reverseKGroup([3,4,5], 2)
↓
Reverse [3,4]
4 → 3 → reverseKGroup([5], 2)
↓
Only 1 node (< k)
return [5]
4 → 3 → 5
2 → 1 → 4 → 3 → 5 ✓
🎯 Key Insights
Insight 1: Finding k-th Node
// Critical helper function
private ListNode getKthNode(ListNode start, int k) {
ListNode curr = start;
while (curr != null && k > 0) {
curr = curr.next;
k--;
}
return curr; // null if < k nodes
}
Why important?
Determines if we have enough nodes to reverse
If null returned → less than k nodes left
Prevents incomplete group reversal
Insight 2: The Reversal Trick
Normal reversal (entire list):
prev = null
while (curr != null)
K-group reversal (partial):
prev = nextGroupStart (not null!)
while (curr != nextGroupStart)
This connects reversed group to next group!
Example:
Reverse [1,2] with next being 3
prev = 3 (not null)
Reverse: 3 ← 1 ← 2
Already connected to next group! ✓
Insight 3: Reconnection Pattern
Before reversal:
prevGroupEnd → groupStart → ... → kthNode → nextGroup
After reversal:
prevGroupEnd → kthNode → ... → groupStart → nextGroup
Two connections needed:
1. prevGroupEnd.next = kthNode (new head)
2. groupStart is now tail (automatically points to nextGroup)
Update: prevGroupEnd = groupStart (for next iteration)
⚠️ Common Mistakes
Mistake 1: Not checking if k nodes exist
// ❌ WRONG - Reverses incomplete groups!
while (head != null) {
// Reverse k nodes without checking
}
// ✓ CORRECT - Check first
ListNode kthNode = getKthNode(prevGroupEnd, k);
if (kthNode == null) {
break; // Don't reverse
}
Mistake 2: Wrong reversal loop condition
// ❌ WRONG - Reverses entire rest of list!
while (curr != null) {
// Reverses beyond k nodes
}
// ✓ CORRECT - Stop at next group
while (curr != nextGroupStart) {
// Reverses exactly k nodes
}
Mistake 3: Forgetting to save nextGroupStart
// ❌ WRONG - Lost reference!
ListNode groupStart = prevGroupEnd.next;
// Start reversing...
// How to connect to next group? Lost!
// ✓ CORRECT - Save before reversing
ListNode nextGroupStart = kthNode.next;
Mistake 4: Not updating prevGroupEnd
// ❌ WRONG - Always connects from dummy!
prevGroupEnd.next = kthNode;
// Forgot: prevGroupEnd = groupStart
// ✓ CORRECT - Update for next iteration
prevGroupEnd = groupStart;
Mistake 5: Off-by-one in getKthNode
// ❌ WRONG - Returns (k+1)-th node
ListNode curr = start;
for (int i = 0; i <= k; i++) {
curr = curr.next;
}
// ✓ CORRECT - Returns k-th node
while (curr != null && k > 0) {
curr = curr.next;
k--;
}
🎯 Pattern Recognition
Problem Type: Group-Based Reversal
Core Pattern: Reverse Linked List + Group Processing
When to Apply:
✓ Reverse in groups/chunks
✓ Process k elements at a time
✓ Conditional reversal based on count
Recognition Keywords:
- "reverse k nodes"
- "groups of k"
- "k at a time"
- "reverse in chunks"
Similar Problems:
- Reverse Linked List (LC 206) - Building block
- Reverse Linked List II (LC 92) - Reverse between positions
- Swap Nodes in Pairs (LC 24) - Special case k=2
Key Components:
┌────────────────────────────────────────────┐
│ Check: Do k nodes exist? │
│ Reverse: Standard reversal on k nodes │
│ Connect: Link groups together │
│ Update: Move to next group │
│ Time: O(n), Space: O(1) iterative │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "I need to reverse in groups of k"
Step 2: "First check if k nodes exist, then reverse"
Step 3: "Connect reversed groups and handle leftover"
Key Points to Mention:
- Check k nodes exist before reversing each group
- Use standard reversal but stop at group boundary
- Dummy node simplifies head handling
- Reconnect groups carefully
- Leave incomplete final group unchanged
- Time: O(n), Space: O(1) iterative
Walk Through Example:
"For [1,2,3,4,5], k=2:
Check first 2 nodes exist: yes
Reverse [1,2] → [2,1]
Connect to rest: [2,1] → [3,4,5]
Check next 2 nodes exist: yes
Reverse [3,4] → [4,3]
Connect: [2,1,4,3] → [5]
Check next 2 nodes: only 1 left
Leave [5] as is
Result: [2,1,4,3,5]"
Why Dummy Node:
"Dummy simplifies handling when first group is reversed.
Otherwise need special logic for new head."
Complexity:
"Each node visited twice: once checking, once reversing.
Total: O(2n) = O(n)
Space: O(1) with iteration, O(n/k) with recursion"
Edge Cases to Mention:
✓ k = 1 → no reversal needed
✓ k = n → reverse entire list
✓ k > n → return as is
✓ Last group < k nodes → leave unchanged
📝 Quick Revision Notes
🎯 Core Concept:
Reverse Nodes in k-Group: Check if k nodes exist, reverse those k nodes only, connect to next group, repeat. Use dummy node for easier reconnection. Critical: save nextGroupStart before reversing! Stop reversal at group boundary (while curr != nextGroupStart). Leave incomplete final group unchanged.
⚡ Quick Implementation (Iterative):
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 reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode curr = head;
ListNode prevGroupEnd = dummy;
// Run infinitely until you find a group less than k elements.
while (true) {
// Break if there are no more k elements to reverse.
// Last group which is less than k elements are no need to reverse.
ListNode kthNode = getKthNode(prevGroupEnd, k);
if(kthNode == null) {
break;
}
// System.out.println("kth node val: " + kthNode.val);
// ListNode currGroupEnd = kthNode; // 3 in case of (1,2,3,4,5)
ListNode currGroupStart = prevGroupEnd.next;
ListNode nextGroupStart = kthNode.next; // which would be curr in the next iteration and will be assigned at the end
curr = currGroupStart;
ListNode prev = nextGroupStart; // The last node of the reversed group must point to nextGroupStart
// Reverse k group here.
while (curr != nextGroupStart) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
prevGroupEnd.next = kthNode; // linking prevGroup with current group (kth node being now moved to the beginning)
prevGroupEnd = currGroupStart; // Old head is now tail
curr = nextGroupStart;
}
return dummy.next;
}
private ListNode getKthNode(ListNode curr, int k) {
while (curr != null && k > 0) {
curr = curr.next;
k--;
}
return curr;
}
public static void main(String[] args) {
Solution t = new Solution();
ListNode list1 = create(Arrays.asList(1, 2, 3, 4, 5));
print(t.reverseKGroup(list1, 3));
print(t.reverseKGroup(create(Arrays.asList(1, 2, 3, 4, 5, 6)), 3));
print(t.reverseKGroup(create(Arrays.asList(1, 2, 3, 4, 5, 6)), 2));
print(t.reverseKGroup(create(Arrays.asList(1, 2, 3, 4, 5, 6)), 1));
print(t.reverseKGroup(create(Arrays.asList(1, 2, 3, 4, 5, 6)), 6));
}
}
🔑 Key Insights:
- Pattern: Group Processing + Reversal
- Check first: getKthNode to verify k nodes
- Save: nextGroupStart before reversing
- Reverse: prev = nextGroupStart (connects!)
- Stop: while (curr != nextGroupStart)
- Reconnect: prevGroupEnd.next = kthNode
- Time: O(n), Space: O(1) ✓
🎪 Memory Aid:
"Check k, save next, reverse group, reconnect!"
"Check → Save → Reverse → Connect!" ✨
⚠️ Critical Pattern:
Reversal with next group connection:
Normal: prev = null
K-group: prev = nextGroupStart
Why?
When reversing [1,2] before 3:
prev = 3
After: 3 ← 1 ← 2
Already connected to next group!
No extra work needed! ✓
🧪 Edge Cases
Case 1: k = 1
Input: head = [1,2,3], k = 1
Output: [1,2,3]
No reversal needed
Case 2: k = n
Input: head = [1,2,3], k = 3
Output: [3,2,1]
Reverse entire list
Case 3: k > n
Input: head = [1,2], k = 3
Output: [1,2]
Less than k nodes, return as is
Case 4: Incomplete last group
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Last 2 nodes unchanged
Case 5: Perfect multiple
Input: head = [1,2,3,4], k = 2
Output: [2,1,4,3]
All groups reversed
All handled correctly! ✓
Related Problems
- Reverse Linked List (LC 206) - Building block (MUST KNOW!)
- Reverse Linked List II (LC 92) - Reverse between positions
- Swap Nodes in Pairs (LC 24) - Special case k=2
- Reverse Words in a String (LC 151) - Similar grouping
Happy practicing! 🎯
Note: This is a HARD problem that combines multiple patterns! It tests: (1) group processing, (2) reversal technique, (3) pointer manipulation, (4) edge case handling. Master this and you've proven you can handle complex linked list problems! This is frequently asked at Amazon, Meta, Google for senior positions. The key insight: check before reversing, save connections, stop at boundaries! 💪✨