Reverse Nodes in k-Group

Hard
2034.

Reverse Nodes in k-Group

Reverse Nodes in k-Group is a hard coding problem on recursion, asked in Amazon, Google, Microsoft and Meta interviews.

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 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

Follow-up: Can you solve it using only O(1) extra memory?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

Follow-up: Can you solve it using only O(1) extra memory?

Hints for Reverse Nodes in k-Group

  1. Hint 1

    Before reversing a block, make sure it is complete: look k nodes ahead from the node before the block.

  2. Hint 2

    Reversing a block in place needs three facts: the node before it, its first node, and the node right after it.

  3. Hint 3

    Start the reversal with prev set 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

  1. Create dummy before head; groupPrev = dummy.
  2. Walk k steps from groupPrev to find kth. If the walk falls off the list, return dummy.next.
  3. Let groupNext = kth.next. Reverse the block: prev = groupNext, cur = groupPrev.next; while cur != groupNext, point cur at prev and step forward.
  4. The block's old first node is now its last: remember it, set groupPrev.next = kth, and make the old first node the new groupPrev. 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 k nodes exist first.
  • Losing the rest of the list: reverse into groupNext, not into null.
  • 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 = first

Java

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