Reverse Nodes in k-Group
Asked at Walmart
Problem
Given the head of a linked list, reverse the nodes k at a time and return the modified list. If the number of nodes is not a multiple of k, the remaining nodes at the end should stay in their original order. Only constant extra memory may be used.
Asked At
| Company | Difficulty | |
|---|---|---|
| Walmart | HARD | View all Walmart questions → |
How to Think About It
Brute force: convert to array, reverse every k elements, and rebuild the list.
Count nodes first to determine how many full k-groups exist.
Reverse each k-group using iterative reversal with three pointers.
Connect the tail of the previous group to the head of the reversed group.
Optimal: count total nodes, then iteratively reverse exactly k nodes per group, linking groups together.
Optimal Approach
First count the total number of nodes to determine how many complete k-groups exist. Use a dummy head node to handle the case where the first group is reversed. For each group, reverse k nodes iteratively by maintaining prev, curr, and next pointers. After reversing a group, connect the previous group tail to the new head, and advance the tail pointer. Repeat for each full group. Time complexity is O(n) with O(1) extra space.
What Trips People Up in Real Interviews
Clarify that only complete k-groups are reversed and leftover nodes remain as-is.
Mention the need to count total nodes first to know how many groups to reverse.
Explain the iterative reversal technique using prev, curr, and next pointers.
Discuss using a dummy head to simplify edge case handling for the first group.
Address the constant space requirement ruling out recursion stack as a solution.
Solution Code
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
def count_nodes(node):
count = 0
while node:
count += 1
node = node.next
return count
total = count_nodes(head)
dummy = ListNode(0, head)
prev_group_tail = dummy
curr = head
while total >= k:
prev = None
group_start = curr
for _ in range(k):
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
prev_group_tail.next = prev
group_start.next = curr
prev_group_tail = group_start
total -= k
return dummy.nextFrequently Asked Questions
What is the Reverse Nodes in k-Group problem?
Given the head of a linked list, reverse the nodes k at a time and return the modified list. If the number of nodes is not a multiple of k, the remaining nodes at the end should stay in their original order. Only constant extra memory may be used.
How do you solve Reverse Nodes in k-Group?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Reverse Nodes in k-Group?
Reverse Nodes in k-Group is asked at Walmart. It is a hard difficulty problem.
What are common mistakes on Reverse Nodes in k-Group?
- Clarify that only complete k-groups are reversed and leftover nodes remain as-is.
- Mention the need to count total nodes first to know how many groups to reverse.
- Explain the iterative reversal technique using prev, curr, and next pointers.
- Discuss using a dummy head to simplify edge case handling for the first group.
- Address the constant space requirement ruling out recursion stack as a solution.