[Hard] 25. Reverse Nodes in k-Group

This is a complex linked list problem that requires reversing nodes in groups of k. The key insight is using recursion to handle the grouping and a helper function to reverse individual groups.

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 should remain as-is
You may not alter the values in the list’s nodes, only the nodes themselves

Examples

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]

Constraints

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

Thinking Process

The solution uses a recursive approach:

Count Check: Verify if there are at least k nodes remaining
Reverse Group: Reverse the first k nodes using a helper function
Recursive Call: Recursively process the remaining list
Connect Groups: Link the reversed group with the result from recursion

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Iterative pointer walk (this problem)	O(n)	O(1)	Traversal, insertion
Dummy head node	O(n)	O(1)	Simplify head-edge cases
Reversal (3-pointer)	O(n)	O(1)	Reverse sublist or full list
Slow/fast pointers	O(n)	O(1)	Middle, cycle, merge lists

Solution

Time Complexity: O(n) - Each node is visited once
Space Complexity: O(n/k) - Recursion stack depth

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() { this.val = 0; this.next = null; }
 *     ListNode(int x) { this.val = x; this.next = null; }
 *     ListNode(int x, ListNode next) { this.val = x; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int count = 0;
        ListNode ptr = head;
        while(count < k && ptr != null) {
            ptr = ptr.next;
            count++;
        }
        if(count == k) {
            ListNode reversedHead = this.reverseLinkedList(head, k);
            head.next = this.reverseKGroup(ptr, k);
            return reversedHead;
        }
        return head;
    }
    public ListNode reverseLinkedList(ListNode head, int k){
        ListNode new_head = null;
        ListNode ptr = head;
        while(k > 0) {
            ListNode next_node = ptr.next;
            ptr.next = new_head;
            new_head = ptr;
            ptr = next_node;
            k--;
        }
        return new_head;
    }
}

Solution Explanation

Approach: Iterative pointer walk (this problem)

Key idea: The solution uses a recursive approach:

How the code works:

Count Check: Verify if there are at least k nodes remaining
Reverse Group: Reverse the first k nodes using a helper function
Recursive Call: Recursively process the remaining list
Connect Groups: Link the reversed group with the result from recursion

Walkthrough — input head = [1,2,3,4,5], k = 2, expected output [2,1,4,3,5]:

Initialize variables from the problem setup.
Apply the main loop / recursion until the condition is met.
Confirm the result matches the expected output.
Step-by-Step Example

Let’s trace through the solution with head = [1,2,3,4,5] and k = 2:

Step 1: Check if we have at least 2 nodes

Count = 2, ptr points to node 3
We have enough nodes, proceed with reversal

Step 2: Reverse first group [1,2]

reverseLinkedList([1,2], 2) returns [2,1]
new_head = 2, head = 1

Step 3: Recursive call on remaining list

reverseKGroup([3,4,5], 2) processes the rest
This will reverse [3,4] to [4,3] and leave [5] as-is

Step 4: Connect the groups

head->next (which is 1) points to the result from recursion
Final result: [2,1,4,3,5]

Helper Function Breakdown

The reverseLinkedList function:

Iterative Reversal: Reverses exactly k nodes
Pointer Swapping: Uses three pointers for safe reversal
Count Control: Uses k counter to limit reversal to exactly k nodes

Common Mistakes

k = 1: No reversal needed, return original list
k = n: Reverse entire list once
Insufficient Nodes: Return remaining nodes unchanged
Empty List: Handle null head gracefully
Incorrect Count Check: Not verifying enough nodes before reversal
Pointer Confusion: Mixing up head pointers after reversal
Infinite Recursion: Not properly handling base cases
Connection Errors: Not properly linking reversed groups

References

LC 25: Reverse Nodes in k-Group on LeetCode
LeetCode Discuss — LC 25: Reverse Nodes in k-Group
LeetCode Editorial (may require premium)

Key Takeaways

Recursive Structure: Each group is processed independently
Count Validation: Always check if there are enough nodes before reversing
Pointer Management: Careful handling of head pointers and connections
Base Case: Return original head if insufficient nodes remain

Robina Li