LeetCode. 25. Reverse Nodes in k-Group

Problem

Approach

Process the list one group at a time. Starting at the first node of a group, walk k - 1 links to find its kth node. If there are fewer than k nodes left, stop: that suffix must remain in its original order. Otherwise, save the node after the group as groupNext, then reverse the group’s links toward groupNext. Initializing the reversed group’s previous pointer to groupNext makes the old first node point to the untouched suffix when the reversal finishes.

The kth node becomes the group’s new head, and the old first node becomes its tail. Connect the previous group’s tail to the new head (or set the overall head for the first group), then continue from the old first node, now the tail. This reuses every input node; it does not allocate replacement list nodes.

For N nodes, each node is visited a constant number of times, so the time complexity is O(N). The algorithm uses O(1) auxiliary space.

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode groupPrevious = null;
        ListNode groupStart = head;

        while (groupStart != null) {
            ListNode kth = groupStart;
            for (int i = 1; i < k && kth != null; i++) {
                kth = kth.next;
            }
            if (kth == null) {
                break;
            }

            ListNode groupNext = kth.next;
            ListNode previous = groupNext;
            ListNode current = groupStart;
            while (current != groupNext) {
                ListNode next = current.next;
                current.next = previous;
                previous = current;
                current = next;
            }

            if (groupPrevious == null) {
                head = kth;
            } else {
                groupPrevious.next = kth;
            }
            groupPrevious = groupStart;
            groupStart = groupNext;
        }

        return head;
    }
}