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.