How Do You Reverse a Linked List in Groups of K?
Learn how to reverse a linked list in groups of k nodes in O(n) time with O(1) space, including a full Python solution.
Expected Interview Answer
Reversing a linked list in groups of k means walking the list k nodes at a time, reversing the pointers within each full group of k while leaving any trailing group smaller than k in its original order, done in O(n) time and O(1) extra space.
The algorithm first checks whether at least k nodes remain from the current position; if fewer than k remain, that final partial group is left untouched. Otherwise it reverses the next k nodes in place using standard iterative pointer reversal, then recursively or iteratively connects the reversed group's tail to the result of processing the rest of the list. Tracking the previous group's tail is essential so it can be rewired to point at the new head of the just-reversed group, stitching all the reversed groups together correctly. Because each node's pointer is touched a constant number of times regardless of k, the whole traversal remains O(n) time with O(1) additional space if done iteratively, or O(n/k) stack space if done recursively.
- O(n) time regardless of group size k
- O(1) extra space with an iterative implementation
- Leaves a trailing partial group untouched, avoiding data loss
- Common building block for problems like k-group palindrome checks
AI Mentor Explanation
Reversing a linked list in groups of k is like re-ordering a long queue of fielders standing in a line, but only flipping the batting order within each complete set of k fielders at a time, leaving any leftover partial set at the end exactly as it was. You check first whether a full group of k fielders remains ahead; if not, that tail group stays untouched. Within a full group, you physically flip who stands where, then connect the last fielder of that flipped group to whoever leads the next flipped (or untouched) group. Doing this group by group down the whole line takes one pass, touching each fielder a fixed number of times no matter how large k is.
Step-by-Step Explanation
Step 1
Check k nodes remain
Walk ahead k steps from the current node; if fewer than k nodes remain, leave this group unreversed.
Step 2
Reverse the group in place
Iteratively flip the next pointers of the k nodes using standard three-pointer reversal.
Step 3
Recurse or iterate on the rest
Process the remaining list the same way, producing the new head of the next processed segment.
Step 4
Stitch the group's tail to the rest
Connect the original group head (now the tail after reversal) to the head returned from processing the remainder.
What Interviewer Expects
- Correctly handle a trailing group smaller than k by leaving it unreversed
- Perform the reversal iteratively with O(1) extra space per group
- Correctly stitch reversed groups together with the right pointer updates
- State overall O(n) time complexity regardless of k
Common Mistakes
- Reversing a trailing partial group that has fewer than k nodes
- Losing the link to the next group after reversing the current one
- Off-by-one errors when counting k nodes ahead before reversing
- Using O(n) extra space (e.g. a stack of all nodes) instead of the O(1) iterative approach
Best Answer (HR Friendly)
“I walk the list k nodes at a time, first checking a full group of k actually exists before flipping it, since a trailing partial group should stay untouched. After reversing a group's pointers, I connect its new tail to wherever the next group starts, and that single pass handles the whole list in linear time with constant extra space.”
Code Example
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_k_group(head, k):
node = head
count = 0
while node and count < k:
node = node.next
count += 1
if count < k:
return head # fewer than k nodes left, leave as is
prev = reverse_k_group(node, k) # process the rest first
curr = head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev # new head of this reversed groupFollow-up Questions
- How would you solve this iteratively instead of recursively to save stack space?
- How would you reverse only every other group of k, leaving the rest untouched?
- What changes if the trailing partial group should also be reversed?
- How would you detect a cycle before attempting this reversal?
MCQ Practice
1. What should happen to a trailing group with fewer than k nodes?
Standard k-group reversal leaves a partial trailing group untouched since it does not form a full group.
2. What is the overall time complexity of reversing a linked list in groups of k?
Every node's pointer is touched a constant number of times regardless of k, giving O(n) overall.
3. What extra space does the iterative version of k-group reversal use?
An iterative implementation only needs a constant number of pointer variables, giving O(1) extra space.
Flash Cards
What happens to a trailing group with fewer than k nodes? — It is left unreversed in its original order.
What is the time complexity of k-group reversal? — O(n), since each node's pointer is touched a constant number of times.
What must be tracked to correctly stitch groups together? — The tail of the previously reversed group, so it can point to the new head of the next group.
What space complexity does the recursive version use? — O(n/k) call stack space, versus O(1) for the iterative version.