Reverse Nodes in k-Group
Problem
Given the head of a linked list and an integer k, reverse the nodes of the list k at a time and return the modified list. Nodes that are not a multiple of k at the end should remain in their original order. You may not alter the values in the nodes, only nodes themselves may be changed.
- The number of nodes in the list is in the range [1, 10⁴]
- 0 ≤ Node.val ≤ 1000
- 1 ≤ k ≤ the length of the linked list
Example
head = [1,2,3,4,5], k = 2[2,1,4,3,5]The list is processed in groups of 2 nodes. The first group [1,2] is reversed to [2,1]. The second group [3,4] is reversed to [4,3]. The last node [5] remains unchanged because it does not form a complete group of size 2.
Approach
Straightforward Solution
A naive approach would be to extract node values into an array, reverse every k-sized segment, and reconstruct the list. This uses extra space and violates the problem's constraint of modifying nodes in place.
Core Observation
Reversing nodes in fixed-size groups requires careful pointer manipulation to reverse sublists while preserving the overall list structure. The key is to identify each k-sized group, reverse it in place, and then connect it properly to the rest of the list.
Path to Optimal
PreviewThe optimal approach is to iterate through the list, identify the kth node from the current group's previous node, and reverse the nodes between the previous node and the kth node in place…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a dummy node to simplify edge cases. For each group, find the kth node using a helper function…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each node is visited a constant number of times: once to find the kth node and once during reversal, resulting in linear time proportional to the list length.
Space
O(1)
The algorithm uses only a fixed number of pointers and variables, performing all operations in place without additional data structures proportional to input size.
Pattern Spotlight
In-place Reversal of a Linked List (Interval Reversal)
When reversing nodes in fixed-size groups, isolate each group by locating its boundaries, reverse pointers within the group in place, and carefully reconnect the reversed group to the rest of the list to maintain overall list integrity.
Solution
| 1 | class Solution:
|
| 2 | def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
|
| 3 | dummy = ListNode(0, head)
|
| 4 | group_prev = dummy
|
| 5 |
|
| 6 | while True:
|
| 7 | kth = self.getKth(group_prev, k)
|
| 8 | if not kth:
|
| 9 | break
|
| 10 | group_next = kth.next
|
| 11 |
|
| 12 | prev, curr = kth.next, group_prev.next
|
| 13 | while curr != group_next:
|
| 14 | tmp = curr.next
|
| 15 | curr.next = prev
|
| 16 | prev = curr
|
| 17 | curr = tmp
|
| 18 |
|
| 19 | tmp = group_prev.next
|
| 20 | group_prev.next = kth
|
| 21 | group_prev = tmp
|
| 22 | return dummy.next
|
| 23 |
|
| 24 | def getKth(self, curr, k):
|
| 25 | while curr and k > 0:
|
| 26 | curr = curr.next
|
| 27 | k -= 1
|
| 28 | return curr |
Step-by-Step Solution
Initialize Dummy Node and Group Boundary Pointer
| 3 | dummy = ListNode(0, head)
|
| 4 | group_prev = dummy
|
Objective
To create a stable anchor before the head and initialize the pointer that tracks the node immediately before the current k-sized group.
Key Insight
The dummy node removes head-edge-case complexity when the first group is reversed, and group_prev gives the algorithm a fixed handle for reconnecting each reversed segment back into the list. This setup is not just convenience; it is what makes the later group-boundary search and reconnection logic uniform across every iteration.
Interview Quick-Check
Core Logic
Use a dummy node so the first reversed group can be reattached without special-case logic for the head.
State & Boundaries
group_prev must always point to the node immediately before the current group so reconnection after reversal is correct.
Common Pitfalls & Bugs
If group_prev is initialized incorrectly, later calls to find the kth node or reconnect the reversed group will corrupt the list.
Locate Each k-Node Group and Prepare for Reversal
To identify the kth node from the current group's previous node, determining the boundaries of the group to reverse.
Reverse Nodes Within the Identified Group In-Place
To reverse the pointers of nodes in the current k-sized group, effectively reversing the sublist in place.
Reconnect the Reversed Group and Advance to Next Segment
To link the reversed group back into the main list and update pointers to prepare for the next group reversal.
Return the New Head of the Modified List
To return the head of the fully processed list after all possible k-group reversals.
4 more steps with full analysis available on Pro.
Line Analysis
This solution has 7 Critical lines interviewers watch for.
curr.next = prevReverse the pointer of the current node to point to prev.
This is the core reversal step, redirecting the current node's next pointer to reverse the list segment.
kth = self.getKth(group_prev, k)Find the kth node from group_prev to determine the group's end.
Locating the kth node defines the boundary of the group to reverse, ensuring only complete groups are processed.
if not kth:Check if the kth node exists; if not, break the loop as fewer than k nodes remain.
This condition prevents partial groups from being reversed, preserving the problem's requirement that incomplete groups remain unchanged.
Full line-by-line criticality + rationale for all 22 lines available on Pro.
Test Your Understanding
Why is it necessary to find the kth node before reversing a group, and what happens if fewer than k nodes remain?
See the answer with Pro.
Related Problems
In-place Reversal of a Linked List pattern
Don't just read it. Drill it.
Reconstruct Reverse Nodes in k-Group from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Reverse Nodes in k-Group drill