Growing Groups, Even Flip
HardLinked List
Problem
A singly linked list is cut into consecutive groups of growing size: the first group has 1 node, the second 2 nodes, the third 3 nodes, and so on. The last group takes whatever nodes remain, so it may be shorter than its intended size.
Reverse the nodes of every group whose actual number of nodes is even, leave the other groups as they are, and return the head. Relink nodes rather than changing values.
Example 1
- Input:
- head = [5, 2, 6, 3, 9, 1, 7, 3, 8, 4]
- Output:
- [5, 6, 2, 3, 9, 1, 4, 8, 3, 7]
Groups: [5], [2, 6], [3, 9, 1], [7, 3, 8, 4]. The groups of size 2 and 4 are reversed.
Example 2
- Input:
- head = [1, 1, 0, 6, 5]
- Output:
- [1, 0, 1, 5, 6]
Groups: [1], [1, 0], [6, 5]. The last group has 2 actual nodes, which is even.
Example 3
- Input:
- head = [2, 1]
- Output:
- [2, 1]
Constraints
- 1 ≤ number of nodes ≤ 10^5
- 0 ≤ node.val ≤ 10^5
Hint
Show the first hint
The intended size grows by one each group, but what decides reversal is the actual size. Count before acting.
Walkthrough
How to approach it
01Clarify before coding
- Is the parity rule about the intended size or the actual size? The actual size: a short last group of 2 nodes is reversed.
- Is the first group (one node) ever reversed? No, a single node has odd size.
- Must I relink nodes? Yes.
02Brute force
Copy the nodes into an array, reverse the index ranges of even-sized groups, and relink everything.
Cost: O(n) time but O(n) extra space for the array.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.