Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Before reversing a group, check that k nodes are left; if not, leave the rest unchanged.
  2. 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