Reverse Nodes in k-Group

This is the hardest of the classic list-reversal problems, and it is hard for one reason: the joins. Reversing k nodes is the loop you already know. Making the node before the group point at the group's new head, and the group's new tail point at whatever comes after, is where candidates lose track.

The clean solution needs only two small adaptations of the reversal loop and one saved pointer. Once you see them, the code is short.

The problem

You are given the head of a list and an integer k. Reverse the nodes in each consecutive group of k. If the last group has fewer than k nodes, leave it as it is. Return the new head. Move the nodes; do not change their values.

• 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8, k = 3 → 3 → 2 → 1 → 6 → 5 → 4 → 7 → 8. The last group, 7 and 8, is shorter than 3, so it stays.
• 1 → 2 → 3 → 4, k = 4 → 4 → 3 → 2 → 1.
• Any list with k = 1 → unchanged.

Constraints: 1 to 5,000 nodes; 1 ≤ k ≤ length; O(1) extra space.

Clarifying questions

• What about a final group shorter than k? Leave it in order.
• Can I change values instead of relinking? No — relink the nodes.
• Is k at most the length? Yes. (If not, the whole list is one short group and stays.)

Approach 1: reverse chunks of values in an array

Read the values into an array, reverse each full chunk of k, and rebuild the list.

1def reverse_k_group_values(head: ListNode | None, k: int) -> ListNode | None:2    """Reverse values chunk by chunk in an array, then rebuild."""3    values = []4    while head is not None:5        values.append(head.value)6        head = head.next7    for start in range(0, len(values) - k + 1, k):8        values[start:start + k] = values[start:start + k][::-1]9    dummy = ListNode()10    tail = dummy11    for value in values:12        tail.next = ListNode(value)13        tail = tail.next14    return dummy.next

Time: O(n). Space: O(n).

The range stops at len(values) − k + 1, so a short final chunk is never reversed. The approach is fast, but it breaks two stated rules: it uses O(n) extra space, and it builds new nodes from values instead of relinking the existing ones. It is useful as a checker — we used it to test the in-place version on 300 random lists — not as an answer.

The key insight

Treat the list as a series of groups, and keep one pointer, group_previous, on the node just before the current group. It starts at a dummy node. For each group:

1. Check that k nodes exist. Walk k steps from group_previous. If you hit None, the rest is a short group — stop.
2. Reverse exactly those k nodes. Use the usual loop, but with two changes. Stop when current reaches group_next (the first node after the group), not None. And start previous at group_next instead of None. That second change is the trick: the first node you flip — the group's old first node, which becomes its new tail — gets pointed at group_next, so the group is reattached to the rest of the list for free.
3. Fix the front join. The node before the group must now point at the group's new head, the old k-th node. And the old first node, now the group's tail, is the group_previous for the next group — so save it before overwriting group_previous.next.

Approach 2: reverse each group in place

1def reverse_k_group(head: ListNode | None, k: int) -> ListNode | None:2    """Reverse each full group of k in place; leave a short tail alone."""3    dummy = ListNode(0, head)4    group_previous = dummy                     # node just before the current group5    while True:6        kth = group_previous                   # 1. is there a full group ahead?7        for _ in range(k):8            kth = kth.next9            if kth is None:10                return dummy.next11        group_next = kth.next                  # first node after the group12        previous, current = group_next, group_previous.next13        while current is not group_next:       # 2. reverse exactly k nodes14            next_node = current.next15            current.next = previous16            previous = current17            current = next_node18        old_first = group_previous.next        # 3. reconnect and move on19        group_previous.next = kth20        group_previous = old_first

The dummy matters here too: the first group's "node before" is the dummy, so the new head of the whole list is simply dummy.next at the end. No special case for the first group.

Dry run on 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8, k = 3:

After group 1, node 1 (the old first node) is the group's tail and already points at 4, thanks to previous starting at group_next. It becomes group_previous for group 2. After group 2, node 4 plays the same role. The check for group 3 hits None after two steps, so the function returns dummy.next, which is node 3.

Time: O(n) — each node is visited once by the checking walk and once by the reversal. Space: O(1) — a fixed set of pointers.

The time bound is worth one more sentence, because the code has a loop inside a loop inside a while True. The outer loop runs once per group, about n / k times. Inside it, the check walks k nodes and the reversal walks the same k nodes. So each group costs about 2k steps, and n / k groups cost about 2n in total — O(n), not O(n · k). The final, short group costs fewer than k steps and is never reversed.

Edge cases

• k = 1: each "group" is one node; reversing it changes nothing. The output equals the input.
• k equal to the length: one group, the whole list reversed.
• Length a multiple of k: the final check hits None on its first step after the last group, and the function returns.
• A short final group: the check fails before any pointer is touched, so those nodes keep their order.

Follow-ups

• Swap Nodes in Pairs: exactly this with k = 2. Many interviewers ask it first.
• Also reverse the final short group: remove the check in step 1 and reverse whatever remains; the loop then ends when group_previous.next is None.
• Reverse every other group of k: after reversing a group, advance group_previous k more nodes without reversing.