Leetcode - 25. Reverse Nodes in k-Group

💡 Approach

The idea is to reverse each group of k nodes while maintaining the correct links to the rest of the list.

Here’s the plan:

1. Use a dummy node before the head to simplify edge case handling.
2. For each group of k nodes:
   • Use a helper getKth function to find the k-th node from the current position.
   • If fewer than k nodes are left, break the loop.
   • Reverse the k nodes using standard in-place reversal logic.
   • Connect the reversed group with the previous and next parts of the list.

This is a constant space, in-place reversal of linked list nodes.

---

🔁 Step-by-step

1. Dummy Node:
   
   A dummy node is created and linked to head to handle edge cases where head itself changes.

2. Find k-th node:
   
   Use a helper function getKth to find the end of the current group. If less than k nodes are left, return null.

3. Reverse nodes in the group:
   
   Using curr, prev, and a tmp pointer, reverse the links inside the current group.

4. Reconnect the group:
   
   After reversal, connect the previous group to the newly reversed group. Update groupPrev to point to the end of this group.

5. Repeat until no more groups.

🧮 Time Complexity

• Time Complexity: O(N)
  
  Each node is visited and reversed exactly once.

• Space Complexity: O(1)
  
  No extra space except for a few pointers.

Diagrams

🧑‍💻 JavaScript Code

// Definition for singly-linked list node
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

/**
 * Reverse nodes of a linked list in groups of size k
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
    let dummy = new ListNode(0, head);
    let groupPrev = dummy;

    while (true) {
        let kth = getKth(groupPrev, k);
        if (kth == null) break;

        let groupNext = kth.next;
        let curr = groupPrev.next;
        let prev = groupNext;

        // Reverse the group
        while (curr !== groupNext) {
            let tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }

        let tmp = groupPrev.next;
        groupPrev.next = kth;
        groupPrev = tmp;
    }

    return dummy.next;
};

/**
 * Helper to get the k-th node from the current node
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
const getKth = (head, k) => {
    let curr = head;
    while (curr && k > 0) {
        curr = curr.next;
        k--;
    }
    return curr;
};

✅ Example

For list: 1 -> 2 -> 3 -> 4 -> 5, and k = 2, the output will be:

2 -> 1 -> 4 -> 3 -> 5

For k = 3:

3 -> 2 -> 1 -> 4 -> 5

🔚 Conclusion

This problem is a beautiful blend of pointer manipulation and clean logic. Mastering problems like these sharpens your understanding of linked lists and in-place algorithms.