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
The 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. This requires a helper function to find the kth node and a loop to reverse pointers within the group. After reversing, update pointers to prepare for the next group. This process repeats until fewer than k nodes remain.
Optimal Approach
Use a dummy node to simplify edge cases. For each group, find the kth node using a helper function. If fewer than k nodes remain, stop. Reverse the nodes in the group by iteratively changing next pointers. Connect the reversed group back to the main list. Move the group_prev pointer to the end of the reversed group and repeat. Return dummy.next as the new head.
Time
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 |
| 1 | class Solution { |
| 2 | public ListNode reverseKGroup(ListNode head, int k) { |
| 3 | ListNode dummy = new ListNode(0, head); |
| 4 | ListNode groupPrev = dummy; |
| 5 | |
| 6 | while (true) { |
| 7 | ListNode kth = getKth(groupPrev, k); |
| 8 | if (kth == null) { |
| 9 | break; |
| 10 | } |
| 11 | ListNode groupNext = kth.next; |
| 12 | |
| 13 | ListNode prev = groupNext; |
| 14 | ListNode curr = groupPrev.next; |
| 15 | while (curr != groupNext) { |
| 16 | ListNode tmp = curr.next; |
| 17 | curr.next = prev; |
| 18 | prev = curr; |
| 19 | curr = tmp; |
| 20 | } |
| 21 | |
| 22 | ListNode tmp = groupPrev.next; |
| 23 | groupPrev.next = kth; |
| 24 | groupPrev = tmp; |
| 25 | } |
| 26 | |
| 27 | return dummy.next; |
| 28 | } |
| 29 | |
| 30 | private ListNode getKth(ListNode curr, int k) { |
| 31 | while (curr != null && k > 0) { |
| 32 | curr = curr.next; |
| 33 | k--; |
| 34 | } |
| 35 | return curr; |
| 36 | } |
| 37 | } |
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
| 6 | while True:
|
| 7 | kth = self.getKth(group_prev, k)
|
| 8 | if not kth:
|
| 9 | break
|
| 24 | def getKth(self, curr, k):
|
| 25 | while curr and k > 0:
|
| 26 | curr = curr.next
|
| 27 | k -= 1
|
| 28 | return curr |
Objective
To identify the kth node from the current group's previous node, determining the boundaries of the group to reverse.
Key Insight
Locating the kth node is essential to know whether a complete group exists to reverse. Using a helper function to traverse k nodes ahead from the current position allows the algorithm to decide whether to proceed or terminate. This step isolates the group boundaries, enabling safe in-place reversal without corrupting the list.
Interview Quick-Check
Core Logic
The helper function `getKth` moves k steps forward from the current node to find the group's end boundary or returns None if fewer than k nodes remain.
State & Boundaries
If `getKth` returns None, it signals that the remaining nodes are fewer than k, so the main loop breaks to leave the tail unchanged.
Common Pitfalls & Bugs
Failing to check for None after `getKth` can cause null pointer errors or incorrect reversal of incomplete groups.
Reverse Nodes Within the Identified Group In-Place
| 10 | group_next = kth.next
|
| 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
|
Objective
To reverse the pointers of nodes in the current k-sized group, effectively reversing the sublist in place.
Key Insight
Reversing a linked list segment in place requires iteratively redirecting each node's next pointer to its predecessor. By initializing `prev` to the node after the kth node (group_next), the reversal loop rewires pointers from the group's start to end, ensuring the reversed segment connects correctly to the rest of the list. This in-place reversal avoids extra space and preserves node integrity.
Interview Quick-Check
Core Logic
The reversal loop iterates from the group's first node to the node after the kth node, redirecting each node's next pointer to the previous node, effectively reversing the group.
State & Boundaries
The loop terminates when the current pointer reaches group_next, ensuring only the k nodes are reversed.
Common Pitfalls & Bugs
Incorrect initialization of `prev` or failure to update pointers in the correct order can break the list or cause cycles.
Reconnect the Reversed Group and Advance to Next Segment
| 19 | tmp = group_prev.next
|
| 20 | group_prev.next = kth
|
| 21 | group_prev = tmp
|
Objective
To link the reversed group back into the main list and update pointers to prepare for the next group reversal.
Key Insight
After reversal, the previous group's tail (group_prev) must point to the new head of the reversed group (kth), and the tail of the reversed group (original group_prev.next) becomes the new group_prev for the next iteration. This careful pointer update maintains list continuity and sets up the next group boundaries without losing track of the list structure.
Interview Quick-Check
Core Logic
Updating `group_prev.next` to `kth` connects the previous part of the list to the reversed group, and moving `group_prev` to the original group's head (now tail) prepares for the next iteration.
State & Boundaries
The pointer `tmp` temporarily stores the original group's head to update `group_prev` after reversal.
Common Pitfalls & Bugs
Failing to update `group_prev` correctly can cause infinite loops or skip nodes in subsequent reversals.
Return the New Head of the Modified List
| 22 | return dummy.next
|
Objective
To return the head of the fully processed list after all possible k-group reversals.
Key Insight
Using a dummy node simplifies edge cases and ensures the head of the new list is accessible via `dummy.next`. Returning this pointer provides the caller with the updated list head, reflecting all in-place reversals.
Interview Quick-Check
Core Logic
Returning `dummy.next` returns the head of the modified list, which may differ from the original head if the first group was reversed.
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.
prev, curr = kth.next, group_prev.nextInitialize pointers for in-place reversal: prev to group_next, curr to group's first node.
Setting prev to group_next ensures the reversed group's tail points correctly to the next segment, and curr starts at the group's head for reversal.
group_prev.next = kthConnect the previous group's tail to the new head of the reversed group.
Updating group_prev.next to kth links the reversed group back into the main list, maintaining list continuity.
group_prev = tmpMove group_prev to the tail of the reversed group to prepare for the next iteration.
Setting group_prev to the original group's head (now tail) positions it correctly for locating the next group's boundaries.
return currReturn the kth node or None if fewer than k nodes remain.
Returning curr signals the boundary of the group to reverse or indicates insufficient nodes to proceed.
dummy = ListNode(0, head)Create a dummy node pointing to the head to simplify edge case handling.
The dummy node acts as a fixed anchor before the list head, allowing uniform reversal logic even when the first group includes the original head, preventing special-case code.
breakExit the loop when fewer than k nodes remain.
Breaking here stops further processing, leaving the tail of the list intact as required.
while curr != group_next:Loop through nodes in the group until reaching group_next.
This loop reverses pointers for exactly k nodes, ensuring the group is reversed in place without affecting nodes beyond the group.
tmp = curr.nextTemporarily store the next node of curr before changing pointers.
Saving curr.next prevents losing access to the remainder of the list during pointer reversal.
tmp = group_prev.nextStore the original group's head before reversal for reconnection.
This node becomes the tail of the reversed group and is used to link to the next group after reversal.
return dummy.nextReturn the new head of the modified list after all reversals.
Returning dummy.next provides the updated list head, reflecting all in-place k-group reversals.
while curr and k > 0:Traverse forward k steps or until the end of the list.
Moving curr forward k times identifies the kth node or detects if fewer than k nodes remain.
group_prev = dummyInitialize group_prev pointer to the dummy node to track the node before the current group.
This pointer marks the node immediately before the group to be reversed, enabling reconnection after reversal and serving as the starting point for locating the kth node.
group_next = kth.nextStore the node following the kth node to mark the start of the next group.
This pointer preserves the connection to the remainder of the list after the current group is reversed, ensuring the list remains connected.
prev = currMove prev forward to the current node after reversal.
Advancing prev tracks the new head of the reversed portion as the loop progresses.
curr = tmpAdvance curr to the next node to continue reversal.
Moving curr forward allows the loop to process the entire group sequentially.
def getKth(self, curr, k):Define helper function to find the kth node from the current node.
This function encapsulates the logic to traverse k nodes ahead, isolating group boundaries cleanly.
curr = curr.nextAdvance curr to the next node in each iteration.
Progressing curr is necessary to count nodes and find the kth node accurately.
k -= 1Decrement k to track remaining steps to reach kth node.
Decreasing k ensures the loop terminates after exactly k steps or earlier if the list ends.
while True:Start an infinite loop to process groups until fewer than k nodes remain.
The loop iterates over the list in k-sized segments, terminating only when no complete group is found, ensuring all possible groups are reversed.
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?
Finding the kth node defines the exact boundaries of the group to reverse, ensuring only complete groups of size k are reversed. If fewer than k nodes remain, the group is left as is to satisfy the problem's requirement that incomplete groups remain unchanged.
Related Problems
Linked Lists 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