Reverse Nodes in k-Group

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.

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]

Approach: Iterative Group Reversal with Dummy Node

This problem is a step up from the standard “Reverse Linked List” because we need to reverse multiple smaller chunks (groups of k) while properly wiring the connections between these chunks.

We can solve this iteratively with a Dummy Node to keep track of the new head and handle edge cases effortlessly.

The core idea is to identify the $k^{th}$ node to establish the boundaries of our current group, reverse the nodes inside that boundary, and carefully reattach the reversed group to the rest of the list.

1. Initialize Dummy: Create a dummy node pointing to head. Create a pointer groupPrev pointing to dummy. This pointer will always sit right before the current group of $k$ we are trying to reverse.
2. Find the $k^{th}$ Node: Write a small helper function to jump k steps forward from groupPrev.
   • If we hit null before taking k steps, we don’t have enough nodes to form a full group. We break the loop and finish.
   • If we find the $k^{th}$ node, we record the node immediately following it (groupNext = kth.next). This is where the next group starts.
3. Reverse the Group:
   • Normally, when reversing a linked list, we initialize prev = null. Here, we initialize prev = groupNext. Why? Because the very first node in our current group (which will become the last node after reversal) needs to point to the start of the next group.
   • We loop and reverse the pointers exactly like a standard linked list reversal, but we stop when our current pointer reaches groupNext.
4. Wire the Connections:
   • After reversal, the $k^{th}$ node is now the new head of this reversed group. We must point groupPrev.next = kth.
   • We need to prepare groupPrev for the next group. The node that used to be at the front of our group (groupPrev.next before the update) is now at the tail of the reversed group. We store this in a temporary variable, and after rewiring, update groupPrev = tmp.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
function reverseKGroup(head, k) {
    let dummy = new ListNode(0, head);
    let groupPrev = dummy;
    
    while (true) {
        // Find the kth node from our current position
        let kth = getKthNode(groupPrev, k);
        
        // If we don't have k nodes left, we are done
        if (!kth) {
            break;
        }
        
        let groupNext = kth.next; // The start of the next group
        
        // Reverse the current group
        let prev = groupNext; // Initialize prev to groupNext to connect the tail!
        let curr = groupPrev.next;
        
        while (curr !== groupNext) {
            let nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        
        // Wire the reversed group back into the main list
        let tmp = groupPrev.next; // The original first node, now the last node of the group
        groupPrev.next = kth;     // Point the previous group's tail to our new head
        groupPrev = tmp;          // Move groupPrev forward for the next iteration
    }
    
    return dummy.next;
}

// Helper function to jump k nodes forward
function getKthNode(curr, k) {
    while (curr !== null && k > 0) {
        curr = curr.next;
        k -= 1;
    }
    return curr;
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the total number of nodes in the linked list. We traverse each node at most twice (once to find the $k^{th}$ node, and once to reverse it).
• Space Complexity: $O(1)$ since we are strictly manipulating pointers in place and not allocating any extra memory or recursion stack.