MANG Problem #7: Reverse Nodes in k-Group (Hard)

1. Problem Statement

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.

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

2. Approach: Recursive Segment Reversal

To solve this, we break the problem into smaller parts:

Check if there are at least k nodes left. If not, return head.
Reverse the first k nodes.
Recursively call the function for the rest of the list and connect it to the tail of our reversed segment.

3. Java Implementation

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode curr = head;
    int count = 0;
    
    // 1. Find the k+1 node
    while (curr != null && count != k) {
        curr = curr.next;
        count++;
    }
    
    // 2. If we found k nodes, reverse them
    if (count == k) {
        curr = reverseKGroup(curr, k); // Reverse the rest recursively
        
        // head - head-pointer to direct part
        // curr - head-pointer to reversed part
        while (count-- > 0) {
            ListNode next = head.next;
            head.next = curr;
            curr = head;
            head = next;
        }
        head = curr;
    }
    return head;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: Instead of trying to reverse the whole list at once, focus only on the First K. Everything after the first K is someone else's problem (the recursive call).
The Constraint: The "if count == k" check is vital. It's the reason why the [5] in the example doesn't get reversed.
The Connection: The line head.next = curr is where the magic happens. It connects the current reversed segment to the next segment's head.

5. Interview Discussion

Interviewer: "What is the space complexity?"
You: "It is $O(N/K)$ due to the recursion stack. We make one recursive call for every group of $K$ nodes."
Interviewer: "Can you do it in $O(1)$ space?"
You: "Yes, by using an iterative approach with a dummy node and four pointers (prev, curr, next, temp) to track boundaries. It's more complex but avoids the stack overhead."