Reverse Nodes in k-Group — Recursive and Iterative Deep Dive

Problem Statement#

LeetCode 25 — Reverse Nodes in k-Group Difficulty: Hard | Pattern: Recursive Group Reversal

Given the head of a linked list, reverse the nodes of the list k at a time and return the modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k, then the remaining nodes at the end should be left as-is (not reversed).

Constraints:

• Number of nodes: 1 <= n <= 5000
• 0 <= Node.val <= 1000
• 1 <= k <= n

Example 1:

Input:  head = [1, 2, 3, 4, 5], k = 2
Output: [2, 1, 4, 3, 5]

Example 2:

Input:  head = [1, 2, 3, 4, 5], k = 3
Output: [3, 2, 1, 4, 5]

Example 3:

Input:  head = [1, 2, 3, 4, 5], k = 1
Output: [1, 2, 3, 4, 5]  (k=1, no reversal needed)

Why This Problem Matters#

Reverse Nodes in k-Group is one of the canonical hard linked list problems asked at every major tech company — Amazon, Google, Facebook, and Microsoft include it in their interview rotations. It tests not just your understanding of linked list reversal, but your ability to:

1. Structure a recursive or iterative solution with clean subproblem decomposition
2. Handle the "partial group" edge case (leave remainder as-is)
3. Correctly reconnect reversed groups to the rest of the list

This problem is a direct extension of "Reverse Linked List II" (LC 92) and acts as the final boss of the linked list reversal pattern family. Mastering it means you can handle any variation: reverse every other group, reverse even groups, reverse with a predicate, etc.

In system design, this operation appears in cache line reordering, instruction resequencing in CPUs, and packet reordering in network buffers. The ability to reverse fixed-size windows in-place is a fundamental primitive.

Companies like Google specifically ask this problem to watch whether you check for k nodes before reversing (the "less than k remaining" edge case) — candidates who miss this produce incorrect output for non-divisible list lengths.

The Core Insight#

The recursive approach is elegant: treat the problem as "reverse the first k nodes, then recurse on the rest."

Two-step check:

1. Count k nodes: Walk forward k steps. If fewer than k nodes exist, return head unchanged (the remaining nodes stay as-is).
2. Reverse the first k nodes: Standard three-pointer reversal.
3. Connect: After reversal, the original head is now the tail of the reversed group. Its next should be the result of reverseKGroup(curr, k) where curr is the first node after the group.

The iterative approach uses a dummy head and processes group by group, maintaining a "previous group's tail" pointer to connect reversed groups.

Visual Dry Run#

Input: [1, 2, 3, 4, 5], k = 2

Recursive trace:

reverseKGroup([1,2,3,4,5], 2):
  Check: 1->2 exists (k=2 found)
  Reverse [1,2]: prev=null, result prev=2
  head (node 1) -> reverseKGroup([3,4,5], 2)
 
reverseKGroup([3,4,5], 2):
  Check: 3->4 exists (k=2 found)
  Reverse [3,4]: result prev=4
  head (node 3) -> reverseKGroup([5], 2)
 
reverseKGroup([5], 2):
  Check: only 1 node (k=2 needed) -> return head = node(5)
 
Back-tracking:
  node(3).next = node(5)   [tail of 2nd group -> result of 3rd call]
  node(1).next = node(4)   [tail of 1st group -> result of 2nd call = 4]
 
Final: 2 -> 1 -> 4 -> 3 -> 5

Pointer state during reversal of first k=2 nodes:

After reversal: 2 -> 1 -> null, curr = 3

Solution (Optimal)#

from typing import Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    # Step 1: Check if k nodes exist
    curr = head
    count = 0
    while curr and count < k:
        curr = curr.next
        count += 1
    if count < k:
        return head  # fewer than k nodes remaining — do not reverse
 
    # Step 2: Reverse the first k nodes
    prev = None
    curr = head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
 
    # Step 3: head is now the tail of the reversed group
    # Connect tail to result of recursion on the rest
    head.next = reverseKGroup(curr, k)
 
    # prev is the new head of this reversed group
    return prev

function reverseKGroup(head, k) {
    // Step 1: Check if k nodes exist
    let curr = head;
    let count = 0;
    while (curr && count < k) {
        curr = curr.next;
        count++;
    }
    if (count < k) return head; // remainder — leave as-is
 
    // Step 2: Reverse the first k nodes
    let prev = null;
    curr = head;
    for (let i = 0; i < k; i++) {
        const nxt = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nxt;
    }
 
    // Step 3: Connect reversed group's tail to recursion result
    head.next = reverseKGroup(curr, k);
 
    return prev; // new head of this group
}

Iterative approach (O(1) space):

def reverseKGroup(head, k):
    dummy = ListNode(0)
    dummy.next = head
    group_prev = dummy
 
    while True:
        # Check if k nodes remain
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if not kth:
                return dummy.next
 
        group_next = kth.next
 
        # Reverse k nodes
        prev = group_next
        curr = group_prev.next
        while curr != group_next:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
 
        # Connect to previous group
        tmp = group_prev.next  # original first node (will be tail after reversal)
        group_prev.next = kth  # kth is now the head of reversed group
        group_prev = tmp

Complexity:

Common Mistakes#

1. Not checking for k nodes before reversing: The most common bug. If you reverse a partial group, the remaining nodes at the end are incorrectly reversed.
2. Losing the connection to the rest of the list: Before reversing, capture the pointer to the node after the current group (curr after the k-step check loop).
3. Returning prev instead of head in the recursion base case: When fewer than k nodes remain, return head unchanged — not prev (which is null).
4. Off-by-one in the k-node check: The check loop should advance exactly k times. Count carefully.
5. Forgetting that head becomes the tail: After reversing k nodes, the original head is now at the end of the reversed group. Its next must be set to the result of the recursive call.

Interview Tips#

• Start with the recursive approach: It is cleaner to explain. State the subproblem: "reverse first k nodes, then recurse on the rest."
• Draw the before/after: Show [1,2,3,4,5] with k=2. Draw arrows before and after each group reversal.
• Handle k=1 explicitly in your trace: With k=1, no reversal happens. Your code handles it correctly because reversing a single node gives the same node back.
• Offer the iterative upgrade: "For constant space, I can use an iterative approach with a dummy head and a group_prev pointer — want me to implement that too?"
• Discuss stack depth: The recursive approach has O(n/k) call stack depth. For large lists, the iterative approach avoids stack overflow.

Follow-up Questions#

1. LeetCode 92 — Reverse Linked List II: Reverse a specific range instead of repeating groups.
2. LeetCode 2074 — Reverse Nodes in Even Length Groups: Variable-size groups with conditional reversal.
3. What if you should also reverse the remainder? Remove the count < k check and always reverse, including partial groups.
4. What if k is larger than n? The k-node check returns head unchanged immediately — no reversal occurs.
5. Can you reverse every other group of k? Add a skip phase after each reverse phase, alternating between the two.

Key Takeaways#

• Check for k nodes before reversing. If fewer than k nodes remain, return head as-is — this is the most critical correctness check.
• After reversing k nodes: original head is now the tail of the reversed group. Set head.next = reverseKGroup(curr, k).
• prev (after reversal) is the new head of the reversed group — return it.
• The recursive approach has O(n/k) stack depth. The iterative approach achieves O(1) space with a dummy head.
• This is the hardest pure linked list problem — mastering it means you can handle LC 92 (partial range), LC 2074 (even groups), and any group reversal variant.
• Expected answer at FAANG: recognize the subproblem, check for k nodes, reverse, recurse. Full code in about 15–20 minutes.