Reverse Nodes in Even Length Groups — Problem & Solution
Reverse Nodes in Even Length Groups solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Reverse Nodes in Even Length Groups is a medium coding problem on simulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Simulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the head of a singly linked list. Cut the list, from the front, into consecutive groups whose intended sizes are 1, 2, 3, 4, … — the first node alone, the next two nodes, the next three, and so on. The last group takes whatever nodes remain, so its actual length may be smaller than its intended size.
Reverse the nodes of every group whose actual length is even, leave the odd-length groups as they are, and return the head of the resulting list.
Example 1
Input: head = [8,1,4,2,7,5,9,3,6,0]
Output: [8,4,1,2,7,5,0,6,3,9]
Explanation: The groups are [8], [1,4], [2,7,5] and [9,3,6,0]. Only the groups of length 2 and 4 are even, so they are reversed.
Example 2
Input: head = [3,7,1,4]
Output: [3,1,7,4]
Explanation: The groups are [3], [7,1] and [4]. The last group was meant to hold three nodes but only one is left — its length is 1, odd, so it stays.
Example 3
Input: head = [2,6,9,1,5]
Output: [2,9,6,5,1]
Explanation: The groups are [2], [6,9] and [1,5]. The last group has only two nodes, an even length, so it is reversed too.
Constraints
The number of nodes in the list is in the range [1, 10^5]0 <= Node.val <= 10^5
Hints for Reverse Nodes in Even Length Groups
Hint 1
The decision for each group depends on its actual length, which only differs from the intended size for the last group — count before you reverse.
Hint 2
Keep a pointer to the node just before the current group. Walk at most
sizenodes ahead to learn the group's real length and the node that follows it.Hint 3
Reversing a run of
knodes in place: start the reversed run pointing at the node after the group, then relink each node in turn; afterwards the old first node of the group is the new tail and the next group's predecessor.
How to solve Reverse Nodes in Even Length Groups
Walk the list group by group, remembering the node before the group. For each group first count how many nodes it really has (at most its intended size), and reverse exactly those nodes in place when the count is even.
Approach
- The first group is the head alone — length 1, never reversed — so start with
prev = headand the intended size2. - While
prev.nextexists, walk fromprev.nextup tosizenodes, counting them incnt;nodeends at the first node after the group. - If
cntis even, reverse thecntnodes: setrev = node, then for each node of the group point it atrevand make it the newrev. Linkprev.next = rev, and moveprevto the group's old first node, which is now its last. - If
cntis odd, just advanceprevbycntnodes. - Increase
sizeby one and continue; returnhead, which never changes.
Why it works
Every group is handled exactly once and only its own links change. Starting the reversed run at the node after the group keeps the rest of the list attached, and the old first node of the group becomes the predecessor of the next group, so the walk continues from the right place.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Deciding by the intended size: a last group meant to hold 5 nodes that only has 4 must be reversed.
- Forgetting to reconnect the reversed group's tail to the following node — the counting walk already found it.
- The head never moves, because the first group has length 1.
Reference solution
Python
from typing import Optional
def reverseEvenLengthGroups(head: Optional[ListNode]) -> Optional[ListNode]:
prev = head # the first group is the head alone: length 1, never reversed
size = 2
while prev.next:
node, cnt = prev.next, 0
while node and cnt < size:
node = node.next
cnt += 1
if cnt % 2 == 0:
first = cur = prev.next
rev = node
for _ in range(cnt):
nxt = cur.next
cur.next = rev
rev = cur
cur = nxt
prev.next = rev
prev = first
else:
for _ in range(cnt):
prev = prev.next
size += 1
return headJava
public static ListNode reverseEvenLengthGroups(ListNode head) {
ListNode prev = head; // the first group is the head alone
int size = 2;
while (prev.next != null) {
ListNode node = prev.next;
int cnt = 0;
while (node != null && cnt < size) { node = node.next; cnt++; }
if (cnt % 2 == 0) {
ListNode first = prev.next, cur = prev.next, rev = node;
for (int i = 0; i < cnt; i++) { ListNode nxt = cur.next; cur.next = rev; rev = cur; cur = nxt; }
prev.next = rev;
prev = first;
} else {
for (int i = 0; i < cnt; i++) prev = prev.next;
}
size++;
}
return head;
}C++
ListNode* reverseEvenLengthGroups(ListNode* head) {
ListNode* prev = head; // the first group is the head alone
int size = 2;
while (prev->next) {
ListNode* node = prev->next;
int cnt = 0;
while (node && cnt < size) { node = node->next; cnt++; }
if (cnt % 2 == 0) {
ListNode *first = prev->next, *cur = prev->next, *rev = node;
for (int i = 0; i < cnt; i++) { ListNode* nxt = cur->next; cur->next = rev; rev = cur; cur = nxt; }
prev->next = rev;
prev = first;
} else {
for (int i = 0; i < cnt; i++) prev = prev->next;
}
size++;
}
return head;
}JavaScript
var reverseEvenLengthGroups = function(head) {
var prev = head, size = 2; // the first group is the head alone
while (prev.next !== null) {
var node = prev.next, cnt = 0;
while (node !== null && cnt < size) { node = node.next; cnt++; }
if (cnt % 2 === 0) {
var first = prev.next, cur = prev.next, rev = node;
for (var i = 0; i < cnt; i++) { var nxt = cur.next; cur.next = rev; rev = cur; cur = nxt; }
prev.next = rev;
prev = first;
} else {
for (var j = 0; j < cnt; j++) prev = prev.next;
}
size++;
}
return head;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.