Reverse Nodes in K-Group Size of Linked List

1. Problem Statement & Overview

The Reverse Nodes in K-Group problem requires taking the head of a singly linked list and an integer K, and reversing groups of K nodes at a time. If the number of remaining nodes at the end is less than K, they must be left as-is without reversal.

Core Objective

• Traverse the linked list and partition it into segments of size K.
• Reverse each individual segment independently.
• Correctly wire the reversed segments back together while maintaining the sequence of any remaining unreversed nodes.
• Return the updated head of the modified linked list.

2. Real-Life Analogy: The Assembly Line Box Packer

Imagine working on a factory conveyor belt where items arrive in a single continuous line.

• Your supervisor tells you: "Pack items in strict boxes of size 3, but flip the order of items inside each box before sealing it. If the final batch has fewer than 3 items, leave them loose in their original order at the end."
• To achieve this, you cannot flip the entire factory line at once. Instead, you isolate a batch of 3 items, flip their internal order, connect the newly flipped batch to your previously completed boxes, and slide down the conveyor belt to the next batch.

3. High-Level Approach & Strategy

A linked list does not allow direct slicing or localized sub-list reversal out of the box. You cannot simply command: reverse(node3, node6).

The Solution Strategy

1. Locate the $K^{th}$ Node: From the current position (tracked by a temp pointer), traverse forward K - 1 times to find the end of the current group.
2. Handle Edge Cases Early: If fewer than K nodes remain (i.e., the $K^{th}$ node returns null), stop the process and attach the remaining nodes as-is.
3. Isolate the Sub-List: Save a reference to the node immediately following the $K^{th}$ node so you don't lose your place on the conveyor belt. Then, temporarily sever the connection by setting kthNode.next = null.
4. Reverse the Sub-List: Pass the isolated segment into a standard linked list reversal function.
5. Reconnect and Track:
   • If it is the first group, update the global head pointer to point to the new head (which is the old $K^{th}$ node).
   • For subsequent groups, connect the tail of the previous group to the new head of the current reversed group.
6. Advance: Move temp to the saved next node and repeat.

4. Step-by-Step Flow Walkthrough (Example with K = 3)

Let us trace a linked list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 with K = 3.

Group 1: Nodes [1, 2, 3]

• temp starts at node 1.
• Find the $K^{th}$ node: Node 3.
• Save the next node: Node 4.
• Isolate the group: Sever the link at node 3 (3.next = null).
• Reverse sub-list [1 -> 2 -> 3] -> Becomes 3 -> 2 -> 1 (with 3 pointing to null).
• Update global head: Since this is the first group, head moves to 3.

Group 2: Nodes [4, 5, 6]

• Connect the previous group's tail (1) to the new group's head (6).
• temp moves to saved next node (4).
• Find the $K^{th}$ node: Node 6.
• Save the next node: Node 7.
• Isolate and reverse [4 -> 5 -> 6] -> Becomes 6 -> 5 -> 4.
• Store the previous group's tail (4) for the next connection.

Group 3: Nodes [7, 8, 9]

• Connect previous tail (4) to new head (9).
• temp moves to 7.
• Find $K^{th}$ node: Node 9.
• Save next node: null.
• Isolate and reverse [7 -> 8 -> 9] -> Becomes 9 -> 8 -> 7.
• Store previous tail (7).

Final Tail Processing

• temp moves past 9 and finds no more nodes (or fewer than K nodes).
• Attach the previousNode.next to the remaining unreversed nodes (if any exist).

5. Algorithmic Pseudocode

Here is the structured pseudocode capturing the exact mechanics described in the lecture:

function reverseKGroup(head, K):
    if head is null or K == 1:
        return head

    temp = head
    prevLast = null
    newHead = null

    while temp is not null:
        // Step 1: Find the K-th node from current temp
        kthNode = getKthNode(temp, K)
        
        // If there are less than K nodes left, attach and break
        if kthNode is null:
            if prevLast is not null:
                prevLast.next = temp
            break

        // Step 2: Preserve the next node before breaking the link
        nextNode = kthNode.next

        // Step 3: Sever the link to isolate the current K-group
        kthNode.next = null

        // Step 4: Reverse the isolated K-group (temp is the head of this sub-list)
        reverseLinkedList(temp)

        // Step 5: Handle head updates for the very first group vs subsequent groups
        if temp == head:
            newHead = kthNode
        else:
            prevLast.next = kthNode

        // Step 6: Update prevLast to the tail of the current reversed group (which is 'temp')
        prevLast = temp

        // Step 7: Move temp to the next node to process the next group
        temp = nextNode

    return newHead ? newHead : head

6. Helper Functions Breakdown

To make the primary algorithm clean, two vital helper routines are utilized:

A. Finding the $K^{th}$ Node

This function walks forward K - 1 times from a given starting node. If it hits null before completing K steps, it returns null (signaling that an incomplete group has been reached).

function getKthNode(curr, k):
    k = k - 1
    while curr is not null and k > 0:
        curr = curr.next
        k = k - 1
    return curr

B. Standard Linked List Reversal

A standard iterative or pointer-manipulation reversal function that reverses pointers within a localized sub-list.

function reverseLinkedList(head):
    prev = null
    curr = head
    while curr is not null:
        nextTemp = curr.next
        curr.next = prev
        prev = curr
        curr = nextTemp
    return prev

7. Complexity Analysis

8. Summary and Key Takeaways

• Problem Core: Reversing elements of a linked list in fixed batches of size K while leaving incomplete tail groups untouched.
• Why Isolation is Needed: Linked lists cannot perform partial range reversals natively; you must isolate a sub-segment by severing its tail (kthNode.next = null) before passing it to a standard reversal routine.
• Pointer Bookkeeping: Crucial pointers (temp, kthNode, nextNode, prevLast) must be meticulously saved and updated to prevent broken references or memory leaks.
• Head Management: The global head pointer updates exactly once during the processing of the first K-group. All subsequent groups attach via the prevLast tracker.
• In-Place Modification: Achieves optimal $O(1)$ auxiliary space complexity by rewiring pointer references directly.