Reverse Nodes in k-Group

• Create a dummy node pointing to head and a prev pointer to dummy.
• Create a stack to store nodes.
• Loop through the list:
  • First, check if there are k nodes available starting from prev.next.
  • If not, break the loop.
  • If yes, push the k nodes onto the stack.
  • Pop nodes from the stack and relink them. prev.next will point to the first popped node. Update prev after each pop.
  • After the group is reversed, link the tail of the reversed group to the start of the next group.
• Return dummy.next.

This method provides a straightforward way to reverse the groups by leveraging the Last-In, First-Out (LIFO) property of a stack.

Algorithm:

1. Create a dummy node that points to the head of the list. This simplifies handling the list's head.
2. Initialize a p pointer to the dummy node. This pointer will track the end of the previously reversed group.
3. Use a while loop to traverse the list. In each iteration, we first check if there are at least k nodes remaining.
4. If a group of k nodes exists, push these k nodes onto a stack.
5. Pop the nodes from the stack one by one and link them back into the list starting from p.next. Update p to point to the last node of the newly reversed group.
6. The next of the new tail of the group should point to the start of the next group.
7. If fewer than k nodes remain, the check at the beginning of the loop will fail, and we return the result.
8. Return dummy.next.

1import java.util.Stack;2 3class Solution {4    public ListNode reverseKGroup(ListNode head, int k) {5        if (head == null || k == 1) return head;6 7        Stack<ListNode> stack = new Stack<>();8        ListNode dummy = new ListNode(0);9        dummy.next = head;10        ListNode p = dummy;11 12        while (true) {13            ListNode check = p.next;14            int i = 0;15            for (; i < k; i++) {16                if (check == null) break;17                check = check.next;18            }19            if (i < k) break; // Not enough nodes20 21            ListNode temp = p.next;22            for (i = 0; i < k; i++) {23                stack.push(temp);24                temp = temp.next;25            }26 27            while (!stack.isEmpty()) {28                p.next = stack.pop();29                p = p.next;30            }31            p.next = temp;32        }33        return dummy.next;34    }35}

• Check if the list contains at least k nodes. If not, return head.
• If it does, reverse the first k nodes of the list.
• The original head node will become the tail of the reversed group.
• Recursively call the function on the (k+1)-th node.
• Link the new tail's next pointer to the result of the recursive call.
• Return the new head of the reversed group.

Recursion provides an elegant way to handle the linked structure of the problem. The main idea is to handle one group at a time and delegate the rest of the list to a recursive call.

Algorithm:

1. Define a base case: if the list has fewer than k nodes, no reversal is needed, so return the current head. To check this, we can first iterate k nodes forward. If we hit null, we are in the base case.
2. If there are at least k nodes, reverse the first k nodes of the list using the standard iterative reversal technique (with prev, curr, next pointers).
3. After reversing, the original head of the group becomes the tail. The next pointer of this new tail should point to the result of the recursive call on the rest of the list (reverseKGroup(next_node, k)).
4. The new head of the reversed group (which was the k-th node originally) is returned.

1class Solution {2    public ListNode reverseKGroup(ListNode head, int k) {3        // 1. Check if there are at least k nodes4        ListNode curr = head;5        int count = 0;6        while (curr != null && count < k) {7            curr = curr.next;8            count++;9        }10 11        // 2. If k nodes exist, reverse them12        if (count == k) {13            // Reverse the first k nodes14            ListNode prev = null;15            ListNode current = head;16            for (int i = 0; i < k; i++) {17                ListNode nextTemp = current.next;18                current.next = prev;19                prev = current;20                current = nextTemp;21            }22 23            // head is now the tail of the reversed group.24            // current is the head of the next part of the list.25            // Recursively call for the rest of the list and link.26            if (current != null) {27                head.next = reverseKGroup(current, k);28            }29 30            // prev is the new head of this reversed group31            return prev;32        } else {33            // 3. If less than k nodes, return head as is34            return head;35        }36    }37}

• Create a dummy node pointing to head.
• Initialize groupPrev to dummy.
• Loop through the list:
  • Find the k-th node of the current group, let's call it kth.
  • If kth is not found, break the loop.
  • Reverse the sublist between groupPrev.next and kth.
  • Connect groupPrev.next to the new head of the reversed group (the old kth node).
  • Update groupPrev to point to the tail of the reversed group (the old start of the group).
• Return dummy.next.

This method avoids both recursion and auxiliary data structures by using a few pointers to keep track of the different parts of the list during the reversal process.

Algorithm:

1. Create a dummy node and point its next to head. This simplifies connections, especially for the first group.
2. Initialize groupPrev to dummy. This pointer will always point to the node just before the current group being processed.
3. Enter a loop that continues as long as there are full groups of k nodes to reverse.
4. In each iteration, first find the k-th node of the current group. Let's call it kth. If kth is null, it means we have fewer than k nodes left, so we break the loop.
5. Identify the start of the current group (groupStart = groupPrev.next) and the start of the next group (nextGroupStart = kth.next).
6. Reverse the sublist from groupStart to kth in place. A common way is to treat nextGroupStart as the prev pointer's initial value in a standard reversal loop.
7. After reversal, the old kth node is the new head of the group, and the old groupStart is the new tail.
8. Connect the previous part of the list to this newly reversed group: groupPrev.next = kth.
9. Update groupPrev to be the tail of the just-reversed group (groupStart) to prepare for the next iteration.
10. Return dummy.next.

1class Solution {2    public ListNode reverseKGroup(ListNode head, int k) {3        if (head == null || k == 1) {4            return head;5        }6 7        ListNode dummy = new ListNode(0);8        dummy.next = head;9 10        ListNode groupPrev = dummy;11 12        while (true) {13            // 1. Find the k-th node of the current group14            ListNode kth = groupPrev;15            for (int i = 0; i < k && kth != null; i++) {16                kth = kth.next;17            }18 19            // If we don't have k nodes, we are done20            if (kth == null) {21                break;22            }23 24            // 2. Identify pointers for reversal and connection25            ListNode groupStart = groupPrev.next;26            ListNode nextGroupStart = kth.next;27 28            // 3. Reverse the k nodes in place29            ListNode prev = nextGroupStart;30            ListNode current = groupStart;31            while (current != nextGroupStart) {32                ListNode nextTemp = current.next;33                current.next = prev;34                prev = current;35                current = nextTemp;36            }37 38            // 4. Connect the reversed group39            groupPrev.next = kth;40 41            // 5. Update groupPrev for the next iteration42            groupPrev = groupStart;43        }44 45        return dummy.next;46    }47}