Reverse Nodes in K-Group

leetcode.com

Among all Linked List problems, Reverse Nodes in K-Group is one of the most challenging and interview-favorite questions because it combines:

• Pointer manipulation
• Linked List reversal
• Recursive thinking (or iterative optimization)

If you've already mastered reversing an entire Linked List, this problem is simply applying that logic repeatedly in chunks of size k.

---

Problem Statement

Given the head of a linked list, reverse the nodes of the list k at a time and return the modified list.

If the number of nodes left is less than k, leave them as they are.

---

Example 1

Input:
1 → 2 → 3 → 4 → 5

k = 2

Output:
2 → 1 → 4 → 3 → 5

---

Example 2

Input:
1 → 2 → 3 → 4 → 5

k = 3

Output:
3 → 2 → 1 → 4 → 5

The last two nodes remain unchanged because they don't form a complete group of size 3.

---

Brute Force Idea

Intuition

Store all nodes in an ArrayList.

Reverse every block of size k inside the list.

Reconnect the nodes.

Although this works, it requires extra memory and ignores the fact that Linked Lists are meant for in-place manipulation.

---

Complexity

Time Complexity: O(N)

Space Complexity: O(N)

---

Optimal Approach

Core Observation

We already know how to reverse an entire Linked List.

The only difference here is:

Instead of reversing the whole list, reverse only k nodes at a time.

Before reversing:

1 → 2 → 3 → 4 → 5 → 6

k = 3

After first reversal:

3 → 2 → 1 → 4 → 5 → 6

After second reversal:

3 → 2 → 1 → 6 → 5 → 4

---

Key Idea

For every group:

Step 1

Check whether k nodes exist.

If fewer than k nodes remain:

return head

because they should not be reversed.

---

Step 2

Reverse exactly k nodes.

Same logic as reversing a Linked List.

---

Step 3

The original head becomes the tail of the reversed group.

Connect it to the answer of the remaining list.

---

Visual Dry Run

Input

1 → 2 → 3 → 4 → 5

k = 2

---

First Group

1 → 2

Reverse:

2 → 1

Remaining:

3 → 4 → 5

---

Second Group

Reverse:

4 → 3

Remaining:

5

---

Final List

2 → 1 → 4 → 3 → 5

---

Recursive Thinking

Suppose we reverse first k nodes:

1 → 2 → 3 → 4 → 5

k = 3

After reversal:

3 → 2 → 1

Now solve:

4 → 5

Recursively.

Connect:

1.next = solve(4 → 5)

---

Why Recursion Fits Naturally

Each group asks the exact same question:

Reverse next k nodes and process the remaining list.

This repetitive structure is a perfect fit for recursion.

---

Optimal Java Solution

public class Solution {

    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode curr = head;

        int count = 0;

        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }

        if (count < k) {
            return head;
        }

        ListNode prev = null;
        ListNode next = null;
        curr = head;

        count = 0;

        while (curr != null && count < k) {

            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;

            count++;
        }

        head.next = reverseKGroup(curr, k);

        return prev;
    }
}

---

Dry Run on Code

Input

1 → 2 → 3 → 4 → 5

k = 2

Check first 2 nodes:

1 → 2

Reverse:

2 → 1

Recursive call on:

3 → 4 → 5

Reverse:

4 → 3

Recursive call on:

5

Less than k nodes remain.

Return as it is.

Final:

2 → 1 → 4 → 3 → 5

---

Complexity Analysis

Time Complexity

O(N)

Each node is visited a constant number of times.

---

Space Complexity

O(N/K)

Recursive stack for each group.

---

Interview Explanation

"I first verify whether a complete group of size k exists. If not, I leave the remaining nodes unchanged. Otherwise, I reverse exactly k nodes using standard linked list reversal logic. After reversing, the original head becomes the tail of the group, so I connect it with the recursively processed remaining list. This ensures every complete block of k nodes gets reversed while preserving the leftover nodes."

---

Pattern Recognition

Whenever you hear:

Reverse every K nodes
Reverse alternate K nodes
Reverse a part of Linked List

Think:

Reverse Linked List + Group Processing

This problem is essentially an extension of the classic Reverse Linked List pattern.

---

Key Takeaway

Don't try to reverse the entire list at once. Think of the Linked List as multiple blocks of size K. Reverse one block, connect it to the result of the remaining blocks, and repeat.

Once you see it as "Reverse Linked List applied repeatedly," the problem becomes much easier to visualize and solve.