Problem Description

You are given the head of a singly-linked list. The task is to group the nodes sequentially into groups of increasing sizes (1, 2, 3, 4, ...) and reverse only the groups that have an even number of nodes.

The grouping works as follows:

• Group 1: Contains the 1st node (size = 1)
• Group 2: Contains the 2nd and 3rd nodes (size = 2)
• Group 3: Contains the 4th, 5th, and 6th nodes (size = 3)
• Group 4: Contains the 7th, 8th, 9th, and 10th nodes (size = 4)
• And so on...

The pattern continues where group k contains k nodes. However, the last group might have fewer nodes than expected if there aren't enough nodes left in the list. The last group can have at most 1 + (size of second-to-last group) nodes.

Your task is to:

1. Identify which groups have an even number of nodes
2. Reverse the order of nodes within those even-length groups
3. Keep odd-length groups unchanged
4. Return the modified linked list

For example, if you have a linked list [1,2,3,4,5,6,7,8,9,10]:

• Group 1: [1] (size 1, odd - no change)
• Group 2: [2,3] (size 2, even - reverse to [3,2])
• Group 3: [4,5,6] (size 3, odd - no change)
• Group 4: [7,8,9,10] (size 4, even - reverse to [10,9,8,7])
• Result: [1,3,2,4,5,6,10,9,8,7]

The challenge involves managing the pointers correctly while reversing specific segments of the linked list and handling the edge case where the last group might be incomplete.

Intuition

The key insight is that we need to process the linked list in chunks of increasing sizes (1, 2, 3, 4, ...) and selectively reverse only the even-sized chunks. This suggests a pattern-based traversal where we keep track of the current group size.

First, let's think about what we need:

1. A way to determine how many nodes belong to each group
2. A mechanism to reverse a specific segment of the linked list
3. A way to connect the reversed segments back to the main list

The mathematical pattern for groups is straightforward - group k should have k nodes. The total number of nodes used up to and including group k is 1 + 2 + 3 + ... + k = k * (k + 1) / 2. This formula helps us determine when to stop creating full groups.

For the reversal process, we need a helper function that can reverse exactly l nodes starting from a given position and properly reconnect them. The trick is to keep track of:

• The node before the segment to reverse (to reconnect the head of reversed segment)
• The first node of the segment (which becomes the last after reversal)
• The node after the segment (to reconnect the tail of reversed segment)

The main algorithm flow becomes:

1. Count total nodes to handle the last group correctly
2. Use a dummy node to simplify edge cases at the head
3. For each group size l from 1 onwards:
   • Check if we have enough nodes for a complete group using the formula (1 + l) * l / 2 <= n
   • If l is even, reverse the next l nodes
   • Move the pointer forward by l positions
   • Increment l for the next group
4. Handle the last group separately since it might be incomplete - calculate remaining nodes as n - l * (l - 1) / 2 and reverse if even

The elegance lies in treating the problem as a sequence of independent reverse operations on specific segments, where the segment sizes follow a predictable pattern and only even-sized segments need modification.

Learn more about Linked List patterns.

Solution Approach

The implementation uses a two-phase approach: first counting the total nodes, then processing groups with selective reversal.

Step 1: Count Total Nodes

n = 0
t = head
while t:
    t = t.next
    n += 1

We traverse the entire list once to get the total count n. This helps us determine when we've reached the last (potentially incomplete) group.

Step 2: Set Up Dummy Node

dummy = ListNode(0, head)
prev = dummy

A dummy node simplifies handling edge cases, especially when the first group needs reversal. The prev pointer tracks the node just before the current group.

Step 3: Helper Function for Reversal

def reverse(head, l):
    prev, cur, tail = None, head, head
    i = 0
    while cur and i < l:
        t = cur.next
        cur.next = prev
        prev = cur
        cur = t
        i += 1
    tail.next = cur
    return prev

This function reverses exactly l nodes starting from head:

• tail saves the original head (which becomes the tail after reversal)
• Standard reversal using three pointers: prev, cur, and temporary t
• After reversing l nodes, tail.next = cur connects the reversed segment to the rest of the list
• Returns the new head of the reversed segment

Step 4: Process Complete Groups

l = 1
while (1 + l) * l // 2 <= n and prev:
    if l % 2 == 0:
        prev.next = reverse(prev.next, l)
    i = 0
    while i < l and prev:
        prev = prev.next
        i += 1
    l += 1

• Start with group size l = 1
• Continue while we have enough nodes for a complete group: (1 + l) * l // 2 <= n
• If group size is even (l % 2 == 0), reverse the next l nodes
• Move prev pointer forward by l positions to reach the end of current group
• Increment l for the next group

Step 5: Handle the Last Incomplete Group

left = n - l * (l - 1) // 2
if left > 0 and left % 2 == 0:
    prev.next = reverse(prev.next, left)

• Calculate remaining nodes: left = n - l * (l - 1) // 2
• The formula l * (l - 1) // 2 gives the total nodes used in all complete groups before group l
• If there are remaining nodes and their count is even, reverse them

Step 6: Return Result

return dummy.next

Return the actual head (skipping the dummy node).

The time complexity is O(n) where we traverse the list twice - once for counting and once for processing. The space complexity is O(1) as we only use a constant amount of extra pointers.

Example Walkthrough

Let's walk through a concrete example with the linked list: [1,2,3,4,5,6,7]

Initial Setup:

• Count total nodes: n = 7
• Create dummy node pointing to head: dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
• Set prev = dummy

Group 1 (size = 1):

• Check: Can we form a complete group? (1+1)*1/2 = 1 ≤ 7 ✓
• Is group size even? 1 % 2 = 1 (odd) → No reversal
• Move prev forward 1 position: prev now points to node 1
• Increment group size: l = 2

Group 2 (size = 2):

• Check: Can we form a complete group? (1+2)*2/2 = 3 ≤ 7 ✓
• Is group size even? 2 % 2 = 0 (even) → Reverse!
• Before reversal: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
• Call reverse(node_2, 2) to reverse nodes [2,3]
  • Save tail = 2 (will become last)
  • Reverse: 3 -> 2
  • Connect: 2 -> 4
• After reversal: 1 -> 3 -> 2 -> 4 -> 5 -> 6 -> 7
• Move prev forward 2 positions: prev now points to node 2
• Increment group size: l = 3

Group 3 (size = 3):

• Check: Can we form a complete group? (1+3)*3/2 = 6 ≤ 7 ✓
• Is group size even? 3 % 2 = 1 (odd) → No reversal
• List remains: 1 -> 3 -> 2 -> 4 -> 5 -> 6 -> 7
• Move prev forward 3 positions: prev now points to node 6
• Increment group size: l = 4

Group 4 (size = 4):

• Check: Can we form a complete group? (1+4)*4/2 = 10 > 7 ✗
• Exit the main loop

Handle Last Incomplete Group:

• Calculate remaining nodes: left = 7 - 3*(3-1)/2 = 7 - 3 = 1
• The last group has only 1 node: [7]
• Is count even? 1 % 2 = 1 (odd) → No reversal

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

The groups were:

• Group 1: [1] - size 1 (odd) → unchanged
• Group 2: [2,3] - size 2 (even) → reversed to [3,2]
• Group 3: [4,5,6] - size 3 (odd) → unchanged
• Group 4: [7] - size 1 (odd, incomplete) → unchanged

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm traverses the linked list multiple times:

• First pass counts the total number of nodes: O(n)
• Main loop processes groups of increasing sizes (1, 2, 3, ..., k) where the sum 1 + 2 + 3 + ... + k ≈ n
• For each group that needs reversing (even-length groups), the reverse function takes O(group_size) time
• The total work done across all groups is bounded by the total number of nodes since each node is visited at most twice (once during normal traversal, once during reversal if in an even-length group)
• Overall: O(n) + O(n) = O(n)

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables like dummy, prev, l, i, left, n are all single values
• The reverse function uses local variables prev, cur, tail, t, i which don't scale with input size
• No recursive calls are made, so no additional call stack space is used
• The algorithm modifies the linked list in-place without creating new nodes

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Calculating the Last Group's Size

One of the most common mistakes is miscalculating how many nodes remain in the last group. Developers often forget that the last group can be incomplete and might use the wrong formula to determine its size.

Pitfall Example:

# WRONG: Assuming the last group always has size 'group_size'
remaining_nodes = group_size  # This is incorrect!

Correct Approach:

# Calculate total nodes used in all complete groups
nodes_processed = group_size * (group_size - 1) // 2
# Calculate actual remaining nodes
remaining_nodes = total_nodes - nodes_processed

2. Losing Nodes During Reversal

When reversing a group, if you don't properly connect the reversed segment back to the rest of the list, you can lose all nodes after that group.

Pitfall Example:

def reverse_group(head, size):
    prev, cur = None, head
    for _ in range(size):
        next_temp = cur.next
        cur.next = prev
        prev = cur
        cur = next_temp
    # WRONG: Forgot to connect the tail to remaining nodes!
    return prev  # This loses all nodes after the reversed group

Correct Approach:

def reverse_group(head, size):
    prev, cur = None, head
    tail = head  # Save the original head (becomes tail after reversal)
    for _ in range(size):
        next_temp = cur.next
        cur.next = prev
        prev = cur
        cur = next_temp
    tail.next = cur  # Critical: Connect reversed group to remaining list
    return prev

3. Not Updating the Previous Group's Connection

After reversing a group, you must update the previous group's last node to point to the new head of the reversed group.

Pitfall Example:

# WRONG: Just reversing without updating connections
if group_size % 2 == 0:
    reverse_group(current_head, group_size)  # Lost the returned new head!

Correct Approach:

if group_size % 2 == 0:
    prev_group_tail.next = reverse_group(prev_group_tail.next, group_size)

4. Traversing Past the End of a Group

When moving to the next group, ensure you traverse exactly the current group's size, not more or less.

Pitfall Example:

# WRONG: Always moving by group_size without checking if nodes exist
for _ in range(group_size):
    prev_group_tail = prev_group_tail.next  # Can cause NullPointer

Correct Approach:

nodes_traversed = 0
while nodes_traversed < group_size and prev_group_tail:
    prev_group_tail = prev_group_tail.next
    nodes_traversed += 1

5. Off-by-One Error in Group Size Calculation

The formula for calculating how many nodes have been used up to group k is critical. Using the wrong formula leads to incorrect group boundaries.

Pitfall Example:

# WRONG formulas that are commonly attempted:
total_used = group_size * group_size // 2  # Missing the arithmetic series
total_used = (group_size * (group_size + 1)) // 2  # This includes current group

Correct Approach:

# For groups 1 through (k-1), total nodes = k*(k-1)/2
total_used_before_current = group_size * (group_size - 1) // 2
# For groups 1 through k, total nodes = k*(k+1)/2
total_including_current = (1 + group_size) * group_size // 2

Solution to Avoid These Pitfalls:

1. Always use a dummy node to simplify edge cases
2. Count total nodes first to know exactly how many nodes you're working with
3. Test with small examples (like 1-10 nodes) and manually verify group boundaries
4. Carefully track pointers and ensure all connections are maintained after reversal
5. Use clear variable names that indicate their purpose (e.g., prev_group_tail instead of just prev)