Skip to content

Volume ITechnology

4.9.11 — Reverse Nodes in k-Group ​

LeetCode 25 · Hard

The problem ​

You are given the head of a linked list and a number k. Reverse the nodes in groups of k: the first k nodes are reversed, then the next k, and so on. If the last group has fewer than k nodes, leave it exactly as it is. You must re-link the nodes, not swap their values.

1 → 2 → 3 → 4 → 5,  k = 2   →   2 → 1 → 4 → 3 → 5
1 → 2 → 3 → 4 → 5,  k = 3   →   3 → 2 → 1 → 4 → 5

The list has up to 5,000 nodes, and k is between 1 and the list's length. The follow-up asks for O(1) extra memory.

What the problem is really asking ​

You already know how to reverse a whole list, from 4.9.1. Reversing one group is the same loop, stopped after k nodes.

The new work is all in the stitching. After a group is reversed, its two ends have swapped places. The group must be reconnected to the node before it and to the node after it. Picture a necklace. You cut out k beads, flip that piece around, and tie it back in. To tie it back, you must keep hold of the bead just before the cut and the bead just after it. Let go of either, and the rest of the necklace falls on the floor.

So the real question is: for each group, which pointers must you hold on to, and in what order do you reconnect them?

The brute force, and where it breaks the rules ​

Copy the values into an array, reverse each chunk of k values in the array, and write them back into the nodes.

python
def reverseKGroup(head, k):
    vals = []
    node = head
    while node:
        vals.append(node.val)
        node = node.next
    for start in range(0, len(vals) - k + 1, k):          # only full groups
        vals[start:start + k] = vals[start:start + k][::-1]
    node = head
    for v in vals:
        node.val = v
        node = node.next
    return head

It is O(n) time, but it uses O(n) extra memory, and it swaps values instead of re-linking nodes. Both break the rules.

The flaw in one sentence: it avoids the pointer work by copying everything out, which is exactly the skill the problem is testing.

The idea ​

Put a dummy node in front of the list. Then handle one group per round.

For each group, four nodes matter:

     group_prev                    group_next
         |                             |
   … → [ A → B → C ] → D → …
           ^       ^
         first    kth

after reversing the group:

   … → [ C → B → A ] → D → …
  • group_prev is the node just before the group. After the reversal, it must point to C, the group's new first node.
  • A was the group's first node and is now its last. It must point to D, the node after the group.
  • kth is the group's last node, C. It becomes the group's first node.
  • group_next is D, the first node after the group.

Each round does three steps.

  1. Check there is a full group. Walk k steps from group_prev. If you run out of nodes first, the remaining group is too short, so stop. This walk also finds kth, and the node after it is group_next.
  2. Reverse the group.
  3. Stitch it back in, and move group_prev to the group's new last node, ready for the next round.

The solution ​

python
class Solution:
    def reverseKGroup(self, head, k: int):
        dummy = ListNode(0, head)                     # (1)
        group_prev = dummy

        while True:
            kth = group_prev                          # (2)
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next                 # (3)
            group_next = kth.next                     # (4)

            prev, curr = group_next, group_prev.next  # (5)
            while curr is not group_next:             # (6)
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt

            new_group_prev = group_prev.next          # (7)
            group_prev.next = kth                     # (8)
            group_prev = new_group_prev               # (9)
ts
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  const dummy = new ListNode(0, head);                // (1)
  let groupPrev: ListNode = dummy;

  while (true) {
    let kth: ListNode | null = groupPrev;             // (2)
    for (let i = 0; i < k; i++) {
      kth = kth!.next;
      if (!kth) return dummy.next;                    // (3)
    }
    const groupNext = kth.next;                       // (4)

    let prev = groupNext, curr = groupPrev.next;      // (5)
    while (curr !== groupNext) {                      // (6)
      const nxt: ListNode | null = curr!.next;
      curr!.next = prev;
      prev = curr;
      curr = nxt;
    }

    const newGroupPrev = groupPrev.next!;             // (7)
    groupPrev.next = kth;                             // (8)
    groupPrev = newGroupPrev;                         // (9)
  }
}

Line by line ​

(1) A dummy node in front of the head. Reversing the first group changes which node is the head of the whole list. With a dummy in front, the first group has a group_prev like every other group, and no special case is needed. At the very start, group_prev is the dummy.

(2) Walk k steps from group_prev to find the last node of this group, kth.

(3) Not enough nodes left. If the walk falls off the end, the remaining group is shorter than k and must stay as it is. Everything before it is already done, so we return the real head, dummy.next.

(4) The node after the group.

(5) Set up the reversal, with one twist. In the plain reversal from 4.9.1, prev starts as None, because the old first node becomes the list's last node and must point at nothing. Here the group sits in the middle of the list. Its old first node must point at group_next, the rest of the list. So we start prev at group_next. Then the normal reversal loop makes that connection automatically, with no fix-up afterwards. curr starts at the group's first node.

(6) Reverse exactly this group. The usual four lines: save the next node, turn the arrow back, step prev forward, step curr forward. The loop stops when curr reaches group_next, the boundary.

(7) Save the group's new last node before it is lost. Right now, group_prev.next still points to the group's original first node, A. After the reversal, A is the group's last node. That is exactly the node that will be group_prev for the next round. Line (8) is about to overwrite group_prev.next, so we must read it now.

(8) Connect the node before the group to the group's new first node, which is kth.

(9) Move on. The next group's group_prev is A.

Trace ​

Take 1 → 2 → 3 → 4 → 5 and k = 2.

Round 1. group_prev is the dummy.

  1. Walk 2 steps: kth is node 2, and group_next is node 3.
  2. Reverse with prev starting at node 3. Node 1 now points to 3, and node 2 points to 1.
  3. new_group_prev is node 1. dummy.next becomes node 2. The list is 2 → 1 → 3 → 4 → 5, and group_prev is node 1.

Round 2. group_prev is node 1.

  1. Walk 2 steps: kth is node 4, and group_next is node 5.
  2. Reverse with prev starting at node 5. Node 3 now points to 5, and node 4 points to 3.
  3. new_group_prev is node 3. Node 1's next becomes node 4. The list is 2 → 1 → 4 → 3 → 5, and group_prev is node 3.

Round 3. group_prev is node 3. Walk: the first step reaches node 5, and the second step reaches None. Line (3) returns.

The final list is 2 → 1 → 4 → 3 → 5. ✓

Complexity, derived ​

Time. Each group's nodes are walked twice: once by the check in line (2), and once by the reversal in line (6). Every node belongs to at most one group, and the leftover short group is walked once by the check. So each node is visited at most twice, which is about 2n steps, or O(n).

Space. A fixed set of pointers, no recursion, and no arrays. So the extra memory is O(1), which meets the follow-up.

Edge cases ​

  • k = 1. Each group is a single node, and reversing one node changes nothing. The list comes back unchanged.
  • k equals the list's length. One group: the whole list is reversed.
  • The length is a multiple of k. Every group is reversed, and the check in the final round hits None at once.
  • A short last group. Left alone, as the trace showed with node 5.

The recursive version ​

You can also write it with recursion: check that k nodes exist, reverse them, and let a recursive call handle the rest of the list, attaching its result after the reversed group. It is shorter, but every group adds a waiting call on the call stack, so it uses O(n / k) memory. The follow-up asks for O(1), so the loop version is the one to give.

Variations you will meet ​

  • Swap Nodes in Pairs. This problem with k = 2. If you can write this page, that one is free.
  • Reverse Linked List II. Reverse one stretch from position left to right. The same stitching, for a single group.
  • Rotate List. Join the tail to the head to make a ring, then cut it at the right place.

The general lesson: when you reverse part of a list, start prev at whatever should follow the reversed part, and save any boundary node before you overwrite the pointer that leads to it.

What the interviewer will push on ​

"Why does prev start at group_next?" So the group's old first node points at the rest of the list automatically, instead of at None.

"How do you know a full group remains?" Walk k steps first, and stop if you hit None. The same walk finds group_next.

"Why save new_group_prev before stitching?" The stitch overwrites the only pointer that leads to it.

"Could you do it with recursion?" Yes, more shortly, but with O(n / k) memory.

One thing to volunteer: draw the four pointers before writing code, and name them out loud. This problem is not hard in idea. It is bookkeeping, and the people who fail it are the ones who start typing before they have the picture.

Next: 4.9.12 LFU Cache. Beyond the NeetCode list: the follow-up interviewers ask right after LRU, where the key to throw out is the one used least often.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet