Algorithm-Day32-Reverse-Nodes-in-Group-lc-25

🧩 Problem Description

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

• Nodes that remain fewer than k at the end should remain in order.
• You may not alter the values in the list’s nodes — only node pointers may be changed.

---

💬 Example

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

💡 Intuition

This is an extension of basic linked list reversal.

• Reversing k nodes at a time → similar to lc-206, but in segments.
• Key steps:
  1. Check if at least k nodes remain.
  2. Reverse k nodes.
  3. Recurse or loop to the next k-group.

✅ Use a helper function to reverse a portion of the list.

---

🔢 Java Code (Recursive)

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;

        // Step 1: Check if we have at least k nodes
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }

        if (count < k) return head;

        // Step 2: Reverse k nodes
        ListNode prev = null;
        curr = head;
        for (int i = 0; i < k; i++) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Step 3: Recursively reverse next k group
        head.next = reverseKGroup(curr, k);

        return prev;
    }
}

---

🔁 Java Code (Iterative with Dummy Node)

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode prevGroupEnd = dummy;

        while (true) {
            ListNode kth = getKthNode(prevGroupEnd, k);
            if (kth == null) break;

            ListNode groupStart = prevGroupEnd.next;
            ListNode nextGroupStart = kth.next;

            // Reverse current k-group
            ListNode prev = kth.next, curr = groupStart;
            while (curr != nextGroupStart) {
                ListNode tmp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = tmp;
            }

            // Connect with previous part
            prevGroupEnd.next = kth;
            prevGroupEnd = groupStart;
        }

        return dummy.next;
    }

    private ListNode getKthNode(ListNode curr, int k) {
        while (curr != null && k > 0) {
            curr = curr.next;
            k--;
        }
        return curr;
    }
}

---

⏱ Time and Space Complexity

• Time Complexity: O(n), each node is visited once
• Space Complexity:
  • Recursive: O(n/k) recursion stack
  • Iterative: O(1)

---

✍️ Summary

• Advanced linked list problem — combines segment reversal, pointer manipulation, and recursion/looping.
• You must understand lc-206 (reverse linked list) first.
• Mastering this problem improves your skill with pointer operations.

Start from simpler problems like lc-24, then build up to this level. Great interview question!