Reverse Nodes in k-Group

Hard· reversal· dummy head

Problem

Reverse the nodes of a linked list k at a time and return the new head. If the number of nodes left at the end is less than k, leave that tail as it is. Only links may change, not node values, and extra memory should be constant.

Examples

Input: head = [1,2,3,4,5], k = 2

Output: [2,1,4,3,5]

Input: head = [1,2,3,4,5], k = 3

Output: [3,2,1,4,5]

Only two nodes remain after the first group, so they stay in order.

Constraints

• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Hints & approach

Hint 1

Before reversing a group, check that k nodes actually remain.

Hint 2

Reverse one group with the standard three-pointer technique.

Hint 3

Keep a pointer to the node before the group so you can reconnect both ends.

Approachtry the hints first

Use a dummy node and a pointer groupPrev that sits before the current group. From groupPrev, walk k steps to find the group's last node; if you run out, stop. Remember groupNext = last.next, then reverse the k nodes so the first node now points to groupNext. Link groupPrev.next to the new front (the old last node) and move groupPrev to the old first node, which is now the group's tail. Repeat until a short group is found.

Time O(n) · Space O(1)

← PreviousMerge k Sorted Lists DoneBack to Linked lists