LeetCode 25: Reverse Nodes in k-Group

 

Reverse Nodes in k-Group - LeetCode Solution (C++)

Reversing nodes in groups of k is a classic linked list problem that tests understanding of pointer manipulation and recursion.

---

Problem Statement

LeetCode 25: Reverse Nodes in k-Group

Given 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, leave the remaining nodes as is.

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]

Example 3:

Input:

head = [1], k = 1

Output:

[1]

---

Optimal Approach - Recursive Reversal in Groups

Key Idea

1. Count k nodes in the list to ensure reversal is possible.
2. Reverse k nodes recursively.
3. Link the reversed group to the next reversed part.
4. Stop if there are fewer than k nodes left.

Time Complexity:

• O(N) where N is the number of nodes.

Space Complexity:

• O(N/k) due to recursion depth.

---

C++ Solution (LeetCode Compatible)

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* temp = head;
        for (int i = 0; i < k; i++) {
            if (!temp) return head;  // If less than k nodes left, return as is
            temp = temp->next;
        }

        ListNode* prev = nullptr;
        ListNode* curr = head;
        ListNode* next = nullptr;
        for (int i = 0; i < k; i++) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        head->next = reverseKGroup(curr, k);
        return prev;
    }
};

---

Step-by-Step Code Explanation

1. Check if k nodes exist: If fewer than k nodes remain, return as is.
2. Reverse first k nodes: Use three pointers (prev, curr, next) to reverse links.
3. Recursively call for next part: Link the last node of reversed part to the next reversed section.
4. Return new head (prev) of reversed k-group.

---

Dry Run / Execution Steps

Input:

head = [1,2,3,4,5], k = 2

Pointer Updates & Swaps

Step	Nodes Being Reversed	Modified List
1	1 ↔ 2	2 → 1 → 3 → 4 → 5
2	3 ↔ 4	2 → 1 → 4 → 3 → 5

Final Output:

[2,1,4,3,5]

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Notes
Iterative Approach	O(N)	O(1)	✅ More efficient, but harder to implement
Brute Force (Using Stack)	O(N)	O(N)	❌ Uses extra memory
Recursive (Best Approach) ✅	O(N)	O(N/k)	✅ Clean & easy to understand

Why Recursive Approach is Best?

✔ Elegant & easy to read.
✔ Handles edge cases naturally.
✔ Maintains O(N) time complexity with manageable space overhead.

---

Conclusion

• Best approach: Recursive Reversal in Groups
• Why? Handles k-group reversals efficiently with O(N) time.
• Alternative: Iterative approach (harder to implement, but O(1) space).
• Practice More:
  • Reverse Linked List
  • Swap Nodes in Pairs

Would you like more LeetCode solutions like this? Let me know! 🚀