Reverse Nodes in k-Group — Solution in Python, Java & C++
Reverse Nodes in k-Group solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on recursion.
Reverse Nodes in k-Group is a hard coding problem on recursion, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Hard
- Topics: Recursion
- Asked at: Amazon, Google, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the head of a linked list and a positive integer k. Split the list, from the front, into consecutive blocks of k nodes and reverse the nodes inside every complete block. If the number of nodes is not a multiple of k, the nodes left over at the end stay in their original order.
Only the links may change — not the values stored in the nodes. Return the head of the modified list.
Example 1
Input: head = [1,2,3,4,5,6,7,8], k = 3
Output: [3,2,1,6,5,4,7,8]
Explanation: The blocks [1,2,3] and [4,5,6] are reversed; the last two nodes do not form a full block and keep their order.
Example 2
Input: head = [4,9,2], k = 1
Output: [4,9,2]
Explanation: Blocks of one node are unchanged by reversal.
Example 3
Input: head = [5,6,7,8], k = 4
Output: [8,7,6,5]
Explanation: With k equal to the length, the whole list is reversed.
Constraints
The number of nodes in the list is n1 <= k <= n <= 50000 <= Node.val <= 1000
Follow-up: Can you solve it using only O(1) extra memory?
Hints for Reverse Nodes in k-Group
Hint 1
Before reversing a block, make sure it is complete: look
knodes ahead from the node before the block.Hint 2
Reversing a block in place needs three facts: the node before it, its first node, and the node right after it.
Hint 3
Start the reversal with
prevset to the node after the block, so the reversed block is already attached to the rest; then hook the node before the block to the block's old last node, and continue from the block's old first node, now its last.
How to solve Reverse Nodes in k-Group
Process the list block by block with a dummy node in front. For each block, find its k-th node; if it does not exist, stop. Otherwise reverse exactly the nodes of the block in place and splice the block back between its neighbours.
Approach
- Create
dummybeforehead;groupPrev = dummy. - Walk
ksteps fromgroupPrevto findkth. If the walk falls off the list, returndummy.next. - Let
groupNext = kth.next. Reverse the block:prev = groupNext,cur = groupPrev.next; whilecur != groupNext, pointcuratprevand step forward. - The block's old first node is now its last: remember it, set
groupPrev.next = kth, and make the old first node the newgroupPrev. Repeat.
Why it works
Each reversal touches only the k nodes of one complete block and leaves it linked to groupNext, so the rest of the list stays attached; relinking groupPrev to kth (the block's new first node) connects it to what came before. An incomplete tail is detected before anything changes, so it keeps its order.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Reversing the final partial block — check that
knodes exist first. - Losing the rest of the list: reverse into
groupNext, not intonull. - A recursive solution is also accepted on LeetCode, but uses O(n / k) stack.
Reference solution
Python
from typing import Optional
def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
group_prev = dummy
while True:
kth = group_prev
for _ in range(k):
kth = kth.next
if kth is None:
return dummy.next
group_next = kth.next
prev, cur = group_next, group_prev.next
while cur is not group_next:
cur.next, prev, cur = prev, cur, cur.next
first = group_prev.next
group_prev.next = kth
group_prev = firstJava
public static ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head), groupPrev = dummy;
while (true) {
ListNode kth = groupPrev;
for (int i = 0; i < k && kth != null; i++) kth = kth.next;
if (kth == null) return dummy.next;
ListNode groupNext = kth.next, prev = groupNext, cur = groupPrev.next;
while (cur != groupNext) { ListNode nx = cur.next; cur.next = prev; prev = cur; cur = nx; }
ListNode first = groupPrev.next;
groupPrev.next = kth;
groupPrev = first;
}
}C++
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(0, head);
ListNode* groupPrev = &dummy;
while (true) {
ListNode* kth = groupPrev;
for (int i = 0; i < k && kth; i++) kth = kth->next;
if (!kth) return dummy.next;
ListNode *groupNext = kth->next, *prev = groupNext, *cur = groupPrev->next;
while (cur != groupNext) { ListNode* nx = cur->next; cur->next = prev; prev = cur; cur = nx; }
ListNode* first = groupPrev->next;
groupPrev->next = kth;
groupPrev = first;
}
}JavaScript
var reverseKGroup = function(head, k) {
var dummy = new ListNode(0, head), groupPrev = dummy;
for (;;) {
var kth = groupPrev;
for (var i = 0; i < k && kth !== null; i++) kth = kth.next;
if (kth === null) return dummy.next;
var groupNext = kth.next, prev = groupNext, cur = groupPrev.next;
while (cur !== groupNext) { var nx = cur.next; cur.next = prev; prev = cur; cur = nx; }
var first = groupPrev.next;
groupPrev.next = kth;
groupPrev = first;
}
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 40 recursion problems · the whole catalogue
Learn the technique: Recursion