Reverse Nodes in k-Group
Reverse a linked list k nodes at a time, leaving any shorter remainder as it is, in O(1) extra space using a dummy head and in-place link reversal.
Updated Medium read: 8 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Copy the nodes into an array | O(n) | O(n) |
| Reverse each group in place | O(n) | O(1) |
The problem
Given the head of a linked list and a whole number k of at least 1, reverse the nodes of the list k at a time and return the new head. If the nodes left over at the end number fewer than k, leave them in their original order.
1 → 2 → 3 → 4 → 5, k = 2 → 2 → 1 → 4 → 3 → 5
1 → 2 → 3 → 4 → 5, k = 3 → 3 → 2 → 1 → 4 → 5
1 → 2 → 3 → 4 → 5, k = 1 → 1 → 2 → 3 → 4 → 5 (nothing changes)The nodes themselves must be rearranged by changing their next references. Swapping the values held in the nodes is not allowed, and the target is O(1) extra space.
No single step here is difficult. What makes the problem hard is the bookkeeping: four connections change for every group, and getting any one of them wrong either loses part of the list or ties it into a loop.
A node, in each language. All the code on this page uses this shape:
JavaScript
// A node is any object with a value and a next.
const node = { value: 1, next: null };Python
class ListNode:
def __init__(self, value, next=None):
self.value = value
self.next = nextApproach 1: copy the nodes into an array
Put a reference to every node into an array. Arrays have indexes, so reversing a block of k is an ordinary swap of positions. Then walk the array and rewrite every next to match the new order.
JavaScript
function reverseKGroupWithArray(head, k) {
const nodes = [];
for (let node = head; node !== null; node = node.next) nodes.push(node);
for (let start = 0; start + k <= nodes.length; start += k) {
let left = start;
let right = start + k - 1;
while (left < right) {
[nodes[left], nodes[right]] = [nodes[right], nodes[left]];
left++;
right--;
}
}
for (let i = 0; i < nodes.length; i++) {
nodes[i].next = nodes[i + 1] ?? null;
}
return nodes[0] ?? null;
}Python
def reverse_k_group_with_array(head, k):
nodes = []
node = head
while node is not None:
nodes.append(node)
node = node.next
for start in range(0, len(nodes) - k + 1, k):
nodes[start : start + k] = reversed(nodes[start : start + k])
for i, node in enumerate(nodes):
node.next = nodes[i + 1] if i + 1 < len(nodes) else None
return nodes[0] if nodes else NoneThe condition start + k <= nodes.length stops before a final block that is too short, which leaves the remainder untouched.
Time O(n). Space O(n) for the array. It is correct and hard to get wrong, which makes it a good first answer and a useful check for the in-place version.
Approach 2: reverse each group in place
This combines two techniques from the linked list pointers pattern: a dummy head, and the link reversal from Reverse Linked List.
The four nodes that matter
For each group, name four nodes:
… → groupPrevious → [ groupStart → … → groupEnd ] → afterGroup → …
└────── k nodes ──────┘groupPrevious: the node just before the group. Itsnextmust be changed to point at the group's new first node.groupStart: the group's first node, which becomes its last.groupEnd: the group's last node, which becomes its first.afterGroup: the node just after the group, where the reversed group must reconnect.
The very first group has nothing before it. A dummy node placed in front of the head gives it a groupPrevious like every other group, so the first group needs no special handling. The final answer is whatever follows the dummy.
The steps for each group
- Find
groupEndby walkingksteps fromgroupPrevious. If the walk runs off the end of the list, fewer thanknodes remain: stop, leaving them as they are. - Reverse the group. This is the usual reversal loop with one change:
previousstarts asafterGroupinstead ofnull. The group's old first node then ends up pointing atafterGroup, which reconnects the tail of the group as a side effect. - Reconnect the front: point
groupPrevious.nextatgroupEnd, the group's new first node. - Move on:
groupStartis now the last node of the reversed group, so it is thegroupPreviousof the next group.
JavaScript
function reverseKGroup(head, k) {
const dummy = { value: null, next: head };
let groupPrevious = dummy;
while (true) {
// 1. Find the last node of the next group; stop if fewer than k remain.
let groupEnd = groupPrevious;
for (let i = 0; i < k && groupEnd !== null; i++) {
groupEnd = groupEnd.next;
}
if (groupEnd === null) break;
const groupStart = groupPrevious.next;
const afterGroup = groupEnd.next;
// 2. Reverse the group, so its old first node points at what follows.
let previous = afterGroup;
let current = groupStart;
while (current !== afterGroup) {
const next = current.next;
current.next = previous;
previous = current;
current = next;
}
// 3. Reconnect the front, then 4. move on.
groupPrevious.next = groupEnd;
groupPrevious = groupStart;
}
return dummy.next;
}Python
def reverse_k_group(head, k):
dummy = ListNode(None, head)
group_previous = dummy
while True:
# 1. Find the last node of the next group; stop if fewer than k remain.
group_end = group_previous
for _ in range(k):
group_end = group_end.next
if group_end is None:
return dummy.next
group_start = group_previous.next
after_group = group_end.next
# 2. Reverse the group, so its old first node points at what follows.
previous = after_group
current = group_start
while current is not after_group:
following = current.next
current.next = previous
previous = current
current = following
# 3. Reconnect the front, then 4. move on.
group_previous.next = group_end
group_previous = group_startafterGroup is saved before the reversal starts, because the reversal overwrites groupEnd.next. The reversal loop stops when current reaches afterGroup, not null, so it touches exactly the k nodes of the group.
Walkthrough
1 → 2 → 3 → 4 → 5, k = 2. D is the dummy node.
| Group | groupPrevious | groupStart | groupEnd | afterGroup | List after the group is reversed and reconnected |
|---|---|---|---|---|---|
| 1 | D | 1 | 2 | 3 | D → 2 → 1 → 3 → 4 → 5 |
| 2 | 1 | 3 | 4 | 5 | D → 2 → 1 → 4 → 3 → 5 |
| 3 | 3 | not found | Only one node left: stop |
After group 1, node 1 is the last node of its group, so it becomes groupPrevious for group 2. For the third group, the walk from node 3 takes one step to node 5 and a second step to null, so the loop ends and node 5 stays where it is.
The result is dummy.next: 2 → 1 → 4 → 3 → 5.
Time O(n): each node is passed twice, once when counting out its group and once when reversing it. Space O(1): a fixed handful of references, however long the list and whatever the value of k.
Why count before reversing
It would be simpler to reverse k nodes straight away and count as you go. The trouble comes at the end of the list. If only two nodes remain and k is 3, those two have already been reversed by the time the shortage is discovered, and they would have to be reversed back.
Counting first costs one extra pass over each group, which does not change the O(n) total, and means a group is never touched unless it is complete.
Try it yourself
Copy a solution from above, add the lines below, and run it. The Python version also needs the ListNode class from the top of the page. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
// Helpers: build a list from an array, and read one back.
const toList = (values) =>
values.reduceRight((next, value) => ({ value, next }), null);
const toArray = (head) => {
const values = [];
for (let node = head; node !== null; node = node.next) {
values.push(node.value);
}
return values;
};
console.log(toArray(reverseKGroup(toList([1, 2, 3, 4, 5]), 2))); // [2, 1, 4, 3, 5]
console.log(toArray(reverseKGroup(toList([1, 2, 3, 4, 5]), 3))); // [3, 2, 1, 4, 5]Python
# Helpers: build a list from a Python list, and read one back.
def to_list(values):
head = None
for value in reversed(values):
head = ListNode(value, head)
return head
def to_values(head):
values = []
while head is not None:
values.append(head.value)
head = head.next
return values
print(to_values(reverse_k_group(to_list([1, 2, 3, 4, 5]), 2))) # [2, 1, 4, 3, 5]
print(to_values(reverse_k_group(to_list([1, 2, 3, 4, 5]), 3))) # [3, 2, 1, 4, 5]The comment after each line is the result you should see.
Common mistakes
- Reading
groupEnd.nextafter the reversal. By then it points backwards, into the group. SaveafterGroupfirst. - Starting the reversal with
previous = null. The group's old first node then points atnull, and everything after the group is cut off. - Forgetting to reconnect the front. Without
groupPrevious.next = groupEnd, the node before the group still points at the group's old first node, which is now its last, and the rest of the group is skipped. - Advancing
groupPrevioustogroupEnd. After the reversal,groupEndis the first node of the group. The node just before the next group isgroupStart. - Returning
head. The original head is now the last node of the first group. Returndummy.next. - Reversing the leftover nodes. A final group of fewer than
knodes must keep its original order.
Original problem: LeetCode 25: Reverse Nodes in k-Group