Reverse Nodes in k-Group

Given a linked list, reverse the nodes of the list k at a time and return the modified list. Nodes in the last group smaller than k should remain in original order.

Why this is worth learning

Checking group size before rewiring is essential: an incomplete final group is not a smaller reversal problem, because its original order must be preserved.

Before coding: one-minute experiment

What does reversing groups of 3 do to 1→2→3→4→5?

Function signature

func ReverseKGroup(head *ListNode, k int) *ListNode

Inputs / outputs

• head: head of the list.
• k: group size.
• Return: head of the modified list.

Example

head = 1->2->3->4->5, k=2
Output: 2->1->4->3->5

Constraints

• 1 <= k <= 100_000
• 0 <= number of nodes <= 100_000

Core idea (near-solution)

Repeated segment reversal works only after identifying each exact segment. A tempting one-pass loop reverses nodes as it counts them, but if the list ends before k nodes it has already changed a suffix the contract says to preserve. Look ahead k nodes from the previous group's tail first. If a complete group exists, save the node after it, reverse only that group, and reconnect both boundaries. Lookahead and reversal each touch nodes a constant number of times; avoiding a second pass through a group is not worth losing the boundary proof.

Invariant: all nodes before the current group are already correctly reversed and connected.

Algorithm (step-by-step)

1. Use a dummy node before head.
2. For each group:
   • Check if there are k nodes ahead; if not, stop.
   • Reverse the k nodes using pointer rewiring.
   • Connect the reversed group to the previous tail.
3. Return dummy.Next.

Correctness sketch

At each group boundary, the processed prefix already consists of correctly reversed full groups and groupPrev is its final node. Look ahead k nodes without modification. If fewer exist, the untouched suffix must remain in original order and the algorithm terminates. Otherwise save the node after the group and reverse exactly the k links, initializing the reversed-chain tail connection to that saved successor. Connect groupPrev to the group's new head and advance groupPrev to its original first node, now its tail. This extends the invariant by one complete group. Each node participates in at most one lookahead and one reversal.

Trace (hand walkthrough)

Example input:
head = 1->2->3->4->5, k=2
Output: 2->1->4->3->5

Walk:
- k=2: reverse [1,2] -> 2->1
- reverse [3,4] -> 4->3
- leave remainder 5 -> 2->1->4->3->5

Pitfalls to avoid

• Reversing a partial group.
• Losing the pointer to the next group during reversal.

Debugging lens

Test k=1, k larger than length, exact multiples, and one node short of a full final group. Check pointer identity to distinguish node reversal from value reassignment.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Count k nodes ahead; if fewer than k, leave the tail unchanged.
• Reverse k nodes and reconnect the segment to the remainder.

Reconstruction checkpoint

For A→B→C→D→E→F→G with k=3, identify the groups, final identity order, and the lookahead that prevents corrupting the suffix.

Return to Linked List · Module quiz