Reverse Nodes in k-Group

Difficulty: Hard
Topics: Linked List, Recursion
Link: https://leetcode.com/problems/reverse-nodes-in-k-group/

Problem Description

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 left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

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]

Constraints:

The number of nodes in the list is n.
1 <= k <= n <= 5000
0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

Solution

1. Problem Deconstruction (500+ words)

Technical Version: We are given a singly-linked list where each node contains an integer value and a pointer to the next node. We must reverse the nodes in contiguous groups of size k, where k is a positive integer ≤ list length. The reversal must be performed by modifying node pointers only, not node values. If the final group has fewer than k nodes, it remains unchanged. The algorithm should return the head of the modified linked list.

Beginner Version: Imagine you have a chain of people holding hands. Every k people should turn around and face the opposite direction. If there aren’t enough people left at the end to form a full group of k, those people stay facing their current direction. You can only change who holds whose hand, not the people themselves.

Mathematical Formulation: Let $L = [n_1, n_2, ..., n_m]$ represent the linked list with m nodes. Let $G_i = [n_{(i-1)k+1}, n_{(i-1)k+2}, ..., n_{ik}]$ be the i-th group of k nodes. For $i = 1$ to $\lfloor m/k \rfloor$ :

Reverse the order of nodes in $G_i$
Set $next$ pointer of last node in $G_{i-1}$ to first node of reversed $G_i$
Set $next$ pointer of last node in reversed $G_i$ to first node of $G_{i+1}$

Constraint Analysis:

Number of nodes n: 1 ≤ n ≤ 5000: Allows O(n²) solutions but O(n) is optimal. Maximum 5000 nodes means ~20KB memory for node storage.
k positive integer ≤ n: k=1 means no reversal needed. k=n means reverse entire list. Must handle k=1 and k=n as edge cases.
Node values 0-1000: Values don’t affect algorithm logic, only pointers matter.
Follow-up O(1) space: Eliminates recursive solutions. Requires iterative pointer manipulation.

Hidden Edge Cases:

Single node lists (n=1)
k equals list length (full reversal)
k=1 (no changes needed)
List length not divisible by k (final partial group)
Empty list (though constraints guarantee n≥1)

2. Intuition Scaffolding

Real-World Metaphor: A train with k-car carriages needs each carriage reversed internally while maintaining the overall train order. Workers must decouple and recouple the cars carefully.

Gaming Analogy: In a RPG inventory system, every k items in your backpack need their order reversed, but you can only change which item points to the next, not the items themselves.

Math Analogy: Think of the list as a permutation. We’re applying a series of block transpositions where each block of size k is reversed, equivalent to applying the permutation $(1 2 ... k)^{-1}$ repeatedly to contiguous subsequences.

Common Pitfalls:

Losing head reference: Forgetting to track the new head after first reversal
Incorrect linking: Failing to connect reversed groups properly
Partial group handling: Accidentally reversing final incomplete group
Pointer confusion: Not saving temporary references before modification
Off-by-one errors: Miscounting k nodes during group segmentation
Cycle creation: Creating circular references during pointer manipulation

3. Approach Encyclopedia

Brute Force (Convert to Array):

def reverseKGroup(head, k):
    # Convert linked list to array
    arr = []
    curr = head
    while curr:
        arr.append(curr.val)
        curr = curr.next
    
    # Reverse k-length segments in array
    for i in range(0, len(arr), k):
        if i + k <= len(arr):
            arr[i:i+k] = arr[i:i+k][::-1]
    
    # Rebuild linked list
    dummy = ListNode(0)
    curr = dummy
    for val in arr:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next

Time Complexity: O(n) for conversion + O(n) for reversal + O(n) for rebuilding = O(n) Space Complexity: O(n) for array storage

Optimal Iterative Approach:

def reverseKGroup(head, k):
    def reverse(head, tail):
        # Reverse segment from head to tail (tail exclusive)
        prev, curr = None, head
        while curr != tail:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        return prev
    
    dummy = ListNode(0)
    dummy.next = head
    prev_group_end = dummy
    
    while True:
        # Check if k nodes remain
        kth_node = prev_group_end
        for _ in range(k):
            kth_node = kth_node.next
            if not kth_node:
                return dummy.next
        
        # Reverse current k-group
        group_start = prev_group_end.next
        next_group_start = kth_node.next
        new_head = reverse(group_start, kth_node.next)
        
        # Reconnect segments
        prev_group_end.next = new_head
        group_start.next = next_group_start
        prev_group_end = group_start

Visualization:

Initial: 1 → 2 → 3 → 4 → 5, k=2
Step 1: Identify group 1-2, reverse to 2 → 1
Step 2: Connect dummy → 2, 1 → 3
Step 3: Identify group 3-4, reverse to 4 → 3  
Step 4: Connect 1 → 4, 3 → 5
Result: 2 → 1 → 4 → 3 → 5

Complexity Proof:

Each node visited twice: O(2n) = O(n)
Constant extra pointers: O(1) space
k-node reversal: O(k) per group, n/k groups = O(n) total

4. Code Deep Dive

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head: ListNode, k: int) -> ListNode:
    # Dummy node handles edge case of head modification
    dummy = ListNode(0)
    dummy.next = head
    prev_group_end = dummy  # Tracks end of previous reversed group
    
    while True:
        # Find k-th node checking for group completeness
        kth_node = prev_group_end
        for i in range(k):
            kth_node = kth_node.next
            if not kth_node:  # Incomplete final group
                return dummy.next
        
        # Critical pointers before reversal
        group_start = prev_group_end.next  # First node of current group
        next_group_start = kth_node.next   # First node of next group
        
        # Reverse current k-group (standard linked list reversal)
        prev, curr = None, group_start
        while curr != next_group_start:  # Reverse until next group start
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        
        # Reconnect reversed group to list
        prev_group_end.next = kth_node  # Connect previous group to new head
        group_start.next = next_group_start  # Connect new tail to next group
        prev_group_end = group_start  # Move to end of current reversed group

Edge Case Handling:

Example 1 (k=2): The loop successfully reverses each pair, with prev_group_end correctly linking groups
Example 2 (k=3): The algorithm reverses first 3 nodes, leaves last 2 unchanged due to k-th node check
Single node: k-th node check fails immediately, returns original list
k=1: Each “reversal” is single node, effectively no change

5. Complexity War Room

Hardware-Aware Analysis:

5000 nodes × 2 pointers per node = ~80KB (fits in L2/L3 cache)
Pointer-chasing pattern causes cache misses but O(n) time dominates
Iterative approach avoids stack overflow from recursion

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Array Conversion	O(n)	O(n)	10/10	✅ Good for clarity
Recursive	O(n)	O(n/k)	8/10	❌ Fails O(1) space
Iterative	O(n)	O(1)	6/10	✅ Optimal

6. Pro Mode Extras

Variants Section:

Reverse alternate k-groups: Skip every other group during reversal
Circular list reversal: Handle case where tail connects back to head
Doubly-linked list: Simpler with prev pointers but same O(n) complexity
Multiple transactions (LC 25): This is exactly that problem

Interview Cheat Sheet:

First: Mention time/space complexity upfront
Key Insight: Use dummy node to handle head modification edge case
Critical Step: Always check for k-node completeness before reversal
Common Mistake: Forgetting to save next_group_start before reversal
Testing Strategy: Test k=1, k=n, n%k≠0 cases manually
Optimization: The O(1) space solution is expected in interviews

#25 - Reverse Nodes in k-Group