25. Reverse Nodes in k-Group

Linked List
Recursion
Two Pointers

TIME

O(n)

SPACE

O(1)

Intuition

Process the list one group at a time. Before touching anything, confirm a full group of k nodes actually exists, the trailing remainder must be left untouched, so the check has to happen first, not after a partial reverse.

The reversal itself is the standard three-pointer walk, with one trick: seed prev with the node after the group rather than null. That way the group's original head (which becomes its tail) already points at the rest of the list when the loop ends, and no separate fix-up is needed.

A dummy node in front of head removes the special case for the very first group, since every group then has a real predecessor to relink.

Approach

Create dummy -> head, set groupPrev = dummy.
Loop:
- Walk k steps from groupPrev to find kth. If it's null, fewer than k nodes remain → stop, leaving them as-is.
- Save groupNext = kth.next.
- Reverse the group: with prev = groupNext and cur = groupPrev.next, repeatedly do nxt = cur.next; cur.next = prev; prev = cur; cur = nxt until cur == groupNext.
- Relink: the group's old head (groupPrev.next) is now its tail, so save it as tmp, set groupPrev.next = kth (the new head), then groupPrev = tmp.
Return dummy.next.

Complexity

Time: O(n), each node is visited once to check the group and once to reverse
Space: O(1), only a few pointers, satisfying the follow-up (a recursive version would use O(n/k) stack)

Edge Cases

k == 1 → the list is returned unchanged
n not a multiple of k → the final partial group stays in original order (Example 1's trailing 5)
k == n → the entire list is reversed once
The group-existence check must precede the reversal, or a partial tail would be wrongly reversed
Values must not be swapped, only pointers are rewired

Code

from typing import Optional


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def reverseKGroup(self, head: Optional["ListNode"], k: int) -> Optional["ListNode"]:
        """
        25. Reverse Nodes in k-Group
        Time: O(n)
        Space: O(1)
        """
        dummy = ListNode(0, head)
        group_prev = dummy

        while True:
            # Find the kth node from group_prev; stop if fewer than k remain.
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if kth is None:
                    return dummy.next

            group_next = kth.next

            # Reverse the group; seeding prev with group_next links the
            # new tail to the rest of the list automatically.
            prev, cur = group_next, group_prev.next
            while cur is not group_next:
                nxt = cur.next
                cur.next = prev
                prev = cur
                cur = nxt

            # The old head is now the group's tail.
            tmp = group_prev.next
            group_prev.next = kth
            group_prev = tmp

/**
 * 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; }
 * }
 */

/**
 * 25. Reverse Nodes in k-Group
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode groupPrev = dummy;

        while (true) {
            // Find the kth node from groupPrev; stop if fewer than k remain.
            ListNode kth = groupPrev;
            for (int i = 0; i < k; i++) {
                kth = kth.next;
                if (kth == null) {
                    return dummy.next;
                }
            }

            ListNode groupNext = kth.next;

            // Reverse the group; seeding prev with groupNext links the
            // new tail to the rest of the list automatically.
            ListNode prev = groupNext, cur = groupPrev.next;
            while (cur != groupNext) {
                ListNode nxt = cur.next;
                cur.next = prev;
                prev = cur;
                cur = nxt;
            }

            // The old head is now the group's tail.
            ListNode tmp = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = tmp;
        }
    }
}