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.

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)

Process the list group by group. For each group, first verify it has k nodes. If yes, reverse that segment in-place and connect it to the previous part.

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

• Invariant: all nodes before the current group are already correctly reversed and connected.
• Pointer rewiring preserves all nodes and changes only their order or links.
• Each step maintains list connectivity and the intended invariant.
• When the traversal ends, the list structure matches the required transformation.

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.

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.