Module 4 · Reversal Pattern

Reverse Nodes in k-Group

HardProblem 10 of 17 10 min read ~30 min to solve LeetCode

Linked ListIn-Place ReversalDummy NodePointer ManipulationGroup Processing

Asked atAmazonGoogleMicrosoftMetaAppleBloomberg

Problem Statement

Given the head of a singly linked list, reverse the nodes of the list k at a time and return the modified list. Nodes must be reversed in place by changing links, not by changing values. If the remaining number of nodes is less than k, leave those trailing nodes in their original order.

Input

The head of a singly linked list and an integer k, the required group size.

Output

The head of the list after every complete group of k nodes has been reversed and any shorter trailing group has been left unchanged.

Constraints

•The number of nodes is n
•1 <= k <= n <= 5000
•0 <= Node.val <= 1000

Examples

Example 1

Input:

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

Output: 2 -> 1 -> 4 -> 3 -> 5

Explanation: The complete groups are **1 -> 2** and **3 -> 4**. Each group is reversed, while the trailing **5** is shorter than **k** and stays as-is.

Example 2

Input:

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

Output: 3 -> 2 -> 1 -> 4 -> 5

Explanation: Only the first three nodes form a complete group. The remaining **4 -> 5** has fewer than three nodes, so it is not reversed.

Learning Objectives

Detect whether a complete group of **k** nodes exists before reversing it.
Reverse one bounded group while preserving the pointer to the next group.
Relink the previous group, reversed group, and next group without losing nodes.
Use **groupPrev**, **kth**, and **groupNext** as stable names for group boundaries.

Intuition

Pattern Recognition

The signal is repeated fixed-size segment reversal. Unlike Reverse Linked List II, the segment boundaries are not given by one pair of positions; you must discover each complete block of k nodes, reverse exactly that block, then advance to the next block. The trailing remainder rule is important: if fewer than k nodes remain, those nodes are not touched.

The pointer trap is losing the next group while reversing the current group. Before changing any links, find the kth node and save groupNext = kth.next. During reversal, seed previous with groupNext so the old group head will point to the next group when it becomes the tail. After reversal, connect groupPrev.next to the old kth node and move groupPrev to the old group head.

Common mistakes

×Reversing a final partial group even though the problem says it must remain unchanged.
×Not saving **groupNext** before rewiring, which can disconnect the rest of the list.
×Moving **groupPrev** to the wrong node after a group; it must become the old group head, now the tail.
×Trying to reverse by swapping values, which violates the pointer-focused intent of the problem.

Algorithm Explanation

Key idea

Treat each complete group as a closed interval from groupPrev.next through kth, with groupNext saved as the first node after the interval. Reverse nodes until current reaches groupNext, then splice the reversed group between groupPrev and groupNext. The old group head becomes the tail and the next groupPrev.

Pointer walkthrough

For head = 1 -> 2 -> 3 -> 4 -> 5 and k = 2, start with dummy -> 1 -> 2 -> 3 -> 4 -> 5 and groupPrev = dummy. The first kth node is 2, so groupNext is 3. Reverse from 1 up to but not including 3, seeding previous as 3. The group becomes 2 -> 1 -> 3, then groupPrev.next is set to 2 and groupPrev moves to 1. For the next group, kth is 4 and groupNext is 5. Reverse 3 -> 4 into 4 -> 3, connect 1 -> 4, and move groupPrev to 3. Only 5 remains, so no complete group exists and it stays attached.

Algorithm

Create dummy and set dummy.next to head.
Keep groupPrev as the node before the next group to consider.
Find the kth node after groupPrev. If it does not exist, stop and return dummy.next.
Save groupNext = kth.next and reverse nodes from groupPrev.next until groupNext is reached.
Save the old group head as groupTail, connect groupPrev.next to kth, then move groupPrev to groupTail.
Repeat until fewer than k nodes remain.

Solutions

Solution: Iterative group reversal with saved boundaries

When to prefer this:

Use this version in interviews when the requirement is O(1) extra space and the interviewer wants explicit pointer bookkeeping. It avoids recursion stack space and makes the incomplete trailing group rule easy to enforce.

Before each reversal, scan exactly k nodes from groupPrev to confirm a complete group and identify kth. Save groupNext, reverse the group with the standard previous-current loop, then reconnect the previous group to the new group head and advance to the new tail.

Step-by-step

Create dummy and initialise groupPrev to it.
Call a helper to find the kth node after groupPrev.
If no such node exists, the remaining nodes are fewer than k, so stop.
Save groupNext = kth.next and reverse the current group by pointing each node back toward previous, which starts at groupNext.
Save the old group head as groupTail, connect groupPrev.next to kth, and move groupPrev to groupTail.
Continue with the next group and finally return dummy.next.

Time

O(n)

Space

O(1)

Each node participates in a bounded scan and one reversal step, and only a constant number of pointers are stored.

Java implementation

Loading…

Dry Run

Sample input

head = 1 -> 2 -> 3 -> 4 -> 5, k = 2. Track each complete group and the saved node after that group.

group	groupPrev before	kth	groupNext	reversed segment	list after relink
1	dummy	2	3	1 -> 2 becomes 2 -> 1	dummy -> 2 -> 1 -> 3 -> 4 -> 5
2	1	4	5	3 -> 4 becomes 4 -> 3	dummy -> 2 -> 1 -> 4 -> 3 -> 5
stop	3	not found	none	5 has fewer than k nodes	dummy -> 2 -> 1 -> 4 -> 3 -> 5

The final partial group contains only 5, so the loop stops before reversing it. Returning dummy.next gives 2 -> 1 -> 4 -> 3 -> 5.

Interview Tips

Talk through the boundary names before coding: groupPrev is before the group, kth is the last node in the group, and groupNext is the first node after it. The safest reversal loop stops at groupNext, not at a counter, because groupNext is the stable boundary saved before rewiring.

Likely follow-ups

How would you write the recursive version, and what extra space would the recursion stack use?
How would the solution change if the final short group also had to be reversed?
Can you reverse alternating groups of **k** nodes while leaving every other group unchanged?
How would you adapt the algorithm for a doubly linked list where **prev** pointers must also be updated?

Key Takeaways

Always prove a complete group exists before reversing it.
Save **groupNext** before changing any links inside the group.
The old group head becomes the new group tail and the next **groupPrev**.
Seeding **previous** with **groupNext** reconnects the tail during the reversal itself.

Reusable template: Repeated segment reversal: find a complete block, save the node after it, reverse up to that boundary, splice the block back, and advance from the new tail.