Reverse Nodes in Even Length Groups — Group Counting Linked List

Problem Statement#

LeetCode 2074 — Reverse Nodes in Even Length Groups Difficulty: Medium | Pattern: Group Counting + Selective Reversal

You are given the head of a linked list. The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of natural numbers: group 1 has 1 node, group 2 has 2 nodes, group 3 has 3 nodes, and so on. Reverse the nodes in each group with an even length, and return the head of the modified list.

Note: The last group may have fewer nodes than its expected size. Its actual length determines whether it should be reversed.

Constraints:

• Number of nodes: 1 <= n <= 10^5
• 0 <= Node.val <= 10^5

Example 1:

Input:  [5, 2, 6, 3, 9, 1, 7, 3, 8, 4]
Output: [5, 6, 2, 3, 9, 1, 4, 8, 3, 7]
Explanation:
  Group 1 (size 1): [5]       — odd length, keep as-is
  Group 2 (size 2): [2, 6]    — even, reverse -> [6, 2]
  Group 3 (size 3): [3, 9, 1] — odd, keep as-is
  Group 4 (size 4): [7, 3, 8, 4] — even, reverse -> [4, 8, 3, 7]

Example 2:

Input:  [1, 1, 0, 6]
Output: [1, 0, 1, 6]
Explanation:
  Group 1 (size 1): [1]     — odd, keep
  Group 2 (size 2): [1, 0]  — even, reverse -> [0, 1]
  Group 3 (actual size 1): [6] — odd, keep

Why This Problem Matters#

This problem is a moderately tricky group traversal question that tests whether you can correctly count group sizes (including the truncated last group), apply reversal only to even-length groups, and maintain correct pointer connectivity throughout.

Amazon and Google use this style of problem — "process the list in groups with some transformation rule" — because it requires sustained attention to pointer state across multiple traversal phases. It is similar in spirit to "Reverse Nodes in k-Group" (LC 25) but with the added twist that group sizes vary and the reversal is conditional.

The key engineering challenge is the last group: it might be shorter than its expected size. You must count how many nodes actually exist in each group before deciding whether to reverse. This "look before you act" requirement is what makes the problem more subtle than it first appears.

In practice, this pattern appears in data formatting tasks — aligning columns, grouping records, and interleaving data streams — where you process a sequence in variable-sized windows with conditional transformations.

The Core Insight#

The algorithm has two parts per group:

Part 1 — Count actual nodes in this group: Walk at most group_size steps to count how many nodes actually exist. The last group may have fewer than group_size nodes.

Part 2 — Reverse if even count: If the actual count is even, apply in-place front insertion reversal (the same technique from LC 92 — Reverse Linked List II). If odd, skip.

After processing, advance prev to the last node of the current group and move to the next group.

The key variable is prev: the last node of the previous group (or head for the first group). This serves as the anchor for in-place reversal — you insert nodes after prev to reverse the group without losing the rest of the list.

Visual Dry Run#

Input: [5, 2, 6, 3, 9, 1, 7, 3, 8, 4]

Group 1 (expected size 1, prev=head=node(5)):

• Count: 1 node — odd, no reversal
• prev advances to node(5)

Group 2 (expected size 2, prev=node(5)):

• Count: 2 nodes [2, 6] — even, reverse
• Front insertion: move node(6) after prev(5)
• List segment: 5 -> 6 -> 2 -> 3 ...
• prev advances to node(2) (tail of reversed group)

Group 3 (expected size 3, prev=node(2)):

• Count: 3 nodes [3, 9, 1] — odd, no reversal
• prev advances to node(1)

Group 4 (expected size 4, prev=node(1)):

• Count: 4 nodes [7, 3, 8, 4] — even, reverse
• After reversal: 1 -> 4 -> 8 -> 3 -> 7
• prev advances to node(7)

Result: [5, 6, 2, 3, 9, 1, 4, 8, 3, 7]

Solution (Optimal)#

from typing import Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def reverseEvenLengthGroups(head: Optional[ListNode]) -> Optional[ListNode]:
    prev = head       # last node of the previous group
    group_size = 2    # expected size of current group
 
    while prev.next:
        # Step 1: Count actual nodes in this group
        node = prev
        count = 0
        while node.next and count < group_size:
            node = node.next
            count += 1
 
        group_size += 1  # move to next expected group size
 
        # Step 2: Reverse group if even length
        if count % 2 == 0:
            # Front insertion reversal: move count-1 nodes after prev
            tail = prev.next   # will become the tail of reversed segment
            curr = tail.next
            for _ in range(count - 1):
                tail.next = curr.next
                curr.next = prev.next
                prev.next = curr
                curr = tail.next
 
        # Step 3: Advance prev to last node of current group
        prev = node
 
    return head

function reverseEvenLengthGroups(head) {
    let prev = head;       // last node of previous group
    let groupSize = 2;     // expected size of current group
 
    while (prev.next) {
        // Step 1: Count actual nodes in this group
        let node = prev;
        let count = 0;
        while (node.next && count < groupSize) {
            node = node.next;
            count++;
        }
 
        groupSize++;
 
        // Step 2: Reverse if even-length group
        if (count % 2 === 0) {
            let tail = prev.next;   // becomes tail after reversal
            let curr = tail.next;
            for (let i = 0; i < count - 1; i++) {
                tail.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
                curr = tail.next;
            }
        }
 
        // Step 3: Advance prev to last node of this group
        prev = node;
    }
 
    return head;
}

Complexity:

Common Mistakes#

1. Forgetting the last group may be shorter: Always count actual nodes with count < group_size AND node.next != null. Never assume a group has its full expected size.
2. Starting group_size at 1 instead of 2: Group 1 always has exactly 1 node (odd), so there is nothing to reverse. You can start the traversal logic from group 2 by initializing prev = head and group_size = 2.
3. Wrong number of front insertions: A group of count nodes needs count - 1 front insertions (the first node stays as the tail anchor).
4. Moving prev incorrectly: After processing a group, prev must advance to the last node of that group (variable node after the counting loop), not just one step.
5. Conflating expected size with actual count: Group 4 expects 4 nodes but might only have 2 if the list ends early. The reversal decision is based on actual count, not expected group_size.

Interview Tips#

• Draw the group structure first: Sketch which positions belong to group 1, 2, 3, etc. before writing code. This prevents off-by-one errors.
• Explain the front insertion trick: "I use the same front insertion reversal from LC 92. The group's first node becomes the tail, and I insert subsequent nodes before it count-1 times."
• Call out the last group edge case: "The last group might be shorter — I always count actual nodes, not expected nodes."
• Mention the group_size starting point: "I start at group 2 since group 1 is always size 1 (odd), so nothing to reverse."
• Trace example 2 ([1,1,0,6]): This has a short last group. Walking through it demonstrates you handle the truncated group correctly.

Follow-up Questions#

1. LeetCode 25 — Reverse Nodes in k-Group: Reverse every group of k (fixed size), leaving remainder as-is.
2. What if you needed to reverse odd-length groups instead? Simply flip the condition to count % 2 != 0.
3. How would you handle groups of size determined by node values? Walk the group until a sentinel value is found instead of counting a fixed number of steps.
4. Can you make this recursive? Yes, process the first group recursively and call again for the rest. Space would be O(n/g) for the call stack where g is average group size.
5. What if the list were doubly linked? Reversal becomes easier since you have prev pointers, but the group counting logic stays the same.

Key Takeaways#

• Groups are sized 1, 2, 3, 4 ... but the last group may be shorter. Always count actual nodes with a bounded walk.
• Reverse only groups with even actual count — use in-place front insertion (same technique as LC 92).
• After processing each group, advance prev to the last node of that group using the counting pointer node.
• Start with prev = head and group_size = 2 to skip the trivially odd group 1.
• Time is O(n) overall since each node is touched at most a constant number of times across the counting and reversal phases.
• This problem is a good bridge between LC 92 (partial reversal) and LC 25 (k-group reversal) — mastering all three gives you complete coverage of in-place list reversal patterns.