The challenge
Reverse nodes in consecutive groups of k. Preserve the last group when it contains fewer than k nodes.
k ≥ 1; the input is acyclic. Relink nodes rather than swapping values.
Example
[1, 2, 3, 4, 5], k = 2 → [2, 1, 4, 3, 5].
Use the walkthrough below to inspect the input and each state change.
See Reverse k-group, step by step
Follow the pointers. Watch each link change.
A1Inspect node links
| Node | Value | Next |
|---|---|---|
| A1 | 1 | A2 |
| A2 | 2 | A3 |
| A3 | 3 | A4 |
| A4 | 4 | A5 |
| A5 | 5 | null |
Read the input
IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.
Start from the input head pointers.View original input
A: 1 (A1) → 2 (A2) → 3 (A3) → 4 (A4) → 5 (A5); parameters: {"k":2}
Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.
Put it into code
Check that the complete group exists before changing any of its links.
Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_k_group(head, k):
if k <= 1:
return head
dummy = Node(next=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, curr = group_next, group_prev.next
while curr is not group_next:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
old_head = group_prev.next
group_prev.next = kth
group_prev = old_head
#include <cstddef>
struct Node {
int val;
Node* next;
Node(int value = 0, Node* link = nullptr)
: val(value), next(link) {}
};
Node* reverse_k_group(Node* head, int k) {
if (k <= 1) return head;
Node dummy(0, head);
Node* group_prev = &dummy;
while (true) {
Node* kth = group_prev;
for (int i = 0; i < k; ++i) {
kth = kth->next;
if (!kth) return dummy.next;
}
Node* group_next = kth->next;
Node* prev = group_next;
Node* curr = group_prev->next;
while (curr != group_next) {
Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
Node* old_head = group_prev->next;
group_prev->next = kth;
group_prev = old_head;
}
}