Reverse Nodes in K-Group Solution

Problem

Given a linked list and a positive integer k, reverse the nodes in groups of exactly k. If the final group has fewer than k nodes, leave those nodes in their original order — only complete groups get reversed.

→

→∅

[1,2,3,4,5]

With k = 2:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Explanation: Pairs (1,2) and (3,4) are reversed; node 5 has no partner so it stays.

With k = 3, the output is [3,2,1,4,5] — only the first complete group of three reverses; [4,5] is untouched because two nodes cannot form a group of three.

Intuition

This is repeated linked list reversal, but you must confirm a full group of k nodes exists before touching any pointers — reversing a partial group at the end is the most common mistake. The key insight is that after reversing a group in-place, the node that was first becomes the tail, and you need to wire that tail to the result of the next group before moving on.

Approach 1 — Recursive

Count k nodes to confirm a full group exists, reverse them, then recurse on the remainder and attach its result to the tail.

Walk k steps; if any step reaches null, return head unchanged (fewer than k nodes remain).
Reverse k nodes in-place using a standard reversal loop, leaving curr pointing at the start of the remaining list.
After the loop, head is the tail of the reversed group.
Set head.next to the result of recursing on curr.
Return prev — the new head of the reversed group.

1def reverseKGroup(head, k):
2    # verify k nodes exist before committing to a reversal
3    curr = head
4    for _ in range(k):
5        if not curr:
6            return head  # partial group — leave as-is
7        curr = curr.next
8
9    prev = None
10    curr = head
11    for _ in range(k):
12        next_node = curr.next
13        curr.next = prev
14        prev = curr
15        curr = next_node
16
17    # head is now the tail; wire it to the reversed next group
18    head.next = reverseKGroup(curr, k)
19    return prev  # prev is the new head of this reversed group

Time: O(n) — each node is visited once to count and once to reverse.
Space: O(n/k) — the recursion depth equals the number of complete groups.

Approach 2 — Iterative

Use a dummy node to eliminate the head-special-case, and a group_prev anchor to relink each reversed group without extra space.

Create a dummy node before head; set group_prev = dummy.
Walk k steps from group_prev to find kth_node; if null is hit, return dummy.next.
Save group_next = kth_node.next (first node of the next group) and group_tail = group_prev.next (old group head, which becomes the tail after reversal).
Reverse k nodes starting from group_prev.next, using group_next as the initial prev — this automatically wires the reversed group's tail to the next group.
Set group_prev.next = prev to connect the previous group to the new head.
Advance group_prev = group_tail and repeat.

1def reverseKGroup(head, k):
2    dummy = ListNode(0)
3    dummy.next = head
4    group_prev = dummy
5
6    while True:
7        # walk k steps to confirm a full group exists
8        kth_node = group_prev
9        for _ in range(k):
10            kth_node = kth_node.next
11            if not kth_node:
12                return dummy.next
13
14        group_next = kth_node.next       # first node after this group
15        group_tail = group_prev.next     # old first node becomes new tail
16
17        # reverse k nodes; initializing prev to group_next wires tail automatically
18        prev = group_next
19        curr = group_prev.next
20        for _ in range(k):
21            next_node = curr.next
22            curr.next = prev
23            prev = curr
24            curr = next_node
25
26        group_prev.next = prev       # link previous group to the new head
27        group_prev = group_tail      # advance anchor to the tail of this group

Time: O(n) — each node is visited once to count and once to reverse.
Space: O(1) — only a fixed number of pointers regardless of list length.

Complexity Summary

Approach	Time	Space	When to use
Recursive	O(n)	O(n/k)	When clarity matters and list length is bounded
Iterative	O(n)	O(1)	Production code or very long lists where stack depth is a concern

Common Mistakes

Reversing the partial final group — always verify k nodes exist before starting the reversal; the count check is what enforces the "leave remainder as-is" rule.
Not saving group_next before the reversal loop — the loop immediately overwrites .next pointers, so kth_node.next must be saved first or the link to the next group is lost.
Returning head instead of prev in the recursive version — after reversal, head is the tail of the group, not the head; prev holds the new head.
Off-by-one when walking to the k-th node — starting the walk from group_prev and taking exactly k steps is cleaner than starting from group_prev.next and taking k-1 steps, where the count is easy to mis-state.
Forgetting to advance group_prev to group_tail — if the anchor stays at the old position, the next group gets relinked into the wrong spot, corrupting the entire list from that point on.

Reverse Nodes in K-Group — Solution