Practice › Linked List
Reverse Nodes in K-Group
Hard · Linked List · Asked at Amazon, Microsoft, Google, Meta, Adobe
Reverse the nodes of the list k at a time. If the number of nodes left at the end is less than k, leave them as they are. Print the resulting list.
Input
First line: n k. Second line: the n node values.
Output
The list after reversing each group.
Constraints
- 1 ≤ k ≤ n ≤ 10^5
For each group: check that k nodes remain, reverse them, and connect the previous group's tail to the new group head.
Example 1
Input
5 2 1 2 3 4 5
Output
2 1 4 3 5
Example 2
Input
5 3 1 2 3 4 5
Output
3 2 1 4 5
Hints
- Before reversing a group, check that k nodes are left; if not, leave the rest unchanged.
- Reverse the k nodes in place, then link the tail of the previous group to the new group head and the old group head (now the group tail) to the next part.
Approach
Keep prevTail (initially a dummy node). For each group starting at start = prevTail.next: walk k steps to make sure the group is complete. Reverse exactly k nodes with the usual prev/cur/next loop; afterwards prev is the new group head and start is the group tail. Set prevTail.next = prev, start.next = cur (the first node after the group), and prevTail = start.
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *next = nullptr;
Node(long long v) : val(v) {}
};
int main() {
int n, k;
cin >> n >> k;
Node dummy(0), *t = &dummy;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
t = t->next = new Node(x);
}
Node *prevTail = &dummy;
while (true) {
Node *check = prevTail->next;
int cnt = 0;
while (check && cnt < k) check = check->next, cnt++;
if (cnt < k) break;
Node *start = prevTail->next, *prev = nullptr, *cur = start;
for (int i = 0; i < k; i++) {
Node *nx = cur->next;
cur->next = prev;
prev = cur;
cur = nx;
}
prevTail->next = prev;
start->next = cur;
prevTail = start;
}
for (Node *p = dummy.next; p; p = p->next) cout << p->val << (p->next ? " " : "\n");
return 0;
}Python solution
import sys
class Node:
def __init__(self, val):
self.val, self.next = val, None
data = list(map(int, sys.stdin.read().split()))
n, k = data[0], data[1]
dummy = tail = Node(0)
for v in data[2 : 2 + n]:
tail.next = Node(v)
tail = tail.next
prev_tail = dummy
while True:
check, cnt = prev_tail.next, 0
while check and cnt < k:
check, cnt = check.next, cnt + 1
if cnt < k:
break
start = prev_tail.next
prev, cur = None, start
for _ in range(k):
cur.next, prev, cur = prev, cur, cur.next
prev_tail.next = prev
start.next = cur
prev_tail = start
out, p = [], dummy.next
while p:
out.append(p.val)
p = p.next
print(*out)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node next;
Node(long v) { val = v; }
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
Node dummy = new Node(0), t = dummy;
for (int i = 0; i < n; i++) t = t.next = new Node(sc.nextLong());
Node prevTail = dummy;
while (true) {
Node check = prevTail.next;
int cnt = 0;
while (check != null && cnt < k) { check = check.next; cnt++; }
if (cnt < k) break;
Node start = prevTail.next, prev = null, cur = start;
for (int i = 0; i < k; i++) {
Node nx = cur.next;
cur.next = prev;
prev = cur;
cur = nx;
}
prevTail.next = prev;
start.next = cur;
prevTail = start;
}
StringBuilder sb = new StringBuilder();
for (Node p = dummy.next; p != null; p = p.next) sb.append(p.val).append(p.next != null ? " " : "");
System.out.println(sb);
}
}Solve Reverse Nodes in K-Group online · All practice problems