Hard

Reverse Nodes in k-Group

Given the `head` of 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` then left-out nodes, in the end, should remain as it is. You may not alter the values in the list's nodes, only nodes themselves may be changed.

Examples

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

Output:[2,1,4,3,5]

Nodes are reversed in groups of 2. Node 5 is left out and remains as is.

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

Output:[3,2,1,4,5]

Nodes are reversed in groups of 3. Nodes 4 and 5 are left out.

Constraints

The number of nodes in the list is n.
1 <= k <= n <= 5000
0 <= Node.val <= 1000

Iterative with Dummy Node (Optimal)

Approach

1. We use a `dummy` node that points to the `head` to handle the changing of the head node seamlessly. 2. We iterate through the list to count the total number of nodes. 3. We loop through the list again. As long as there are at least `k` nodes left, we reverse a group of `k` nodes. 4. To reverse a group, we use a standard linked list reversal. We maintain a `prevGroupTail` pointer (initially `dummy`) that connects to the new head of the reversed group. 5. Inside the group, we reverse `k` nodes, adjusting `next` pointers. 6. After reversing a group, the node that was originally the first in the group becomes the last, so it becomes our new `prevGroupTail` for the next iteration. 7. We decrement our node count by `k` and repeat until fewer than `k` nodes remain.

Complexity Analysis

Time Complexity

O(N)

Space Complexity

O(1)

This approach reverses in O(1) auxiliary space without using recursion.

Solution.java

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode reverseKGroup(ListNode head, int k) {13        if (head == null || k == 1) return head;14        15        ListNode dummy = new ListNode(0);16        dummy.next = head;17        18        ListNode curr = head;19        int count = 0;20        while (curr != null) {21            count++;22            curr = curr.next;23        }24        25        ListNode prevGroupTail = dummy;26        27        while (count >= k) {28            curr = prevGroupTail.next;29            ListNode prev = null;30            ListNode next = null;31            32            // Reverse k nodes33            for (int i = 0; i < k; i++) {34                next = curr.next;35                curr.next = prev;36                prev = curr;37                curr = next;38            }39            40            // Connect the reversed group with the previous and next parts41            ListNode nextGroupHead = prevGroupTail.next;42            prevGroupTail.next.next = curr; // connect tail of reversed group to next part43            prevGroupTail.next = prev;      // connect prev part to head of reversed group44            45            prevGroupTail = nextGroupHead;  // update prevGroupTail for next iteration46            count -= k;47        }48        49        return dummy.next;50    }51}