Reverse nodes in even-length linked-list groups
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
### Problem
Given the head of a singly linked list, you will traverse the list in **contiguous groups** of increasing size: the 1st group has size 1, the 2nd group has size 2, the 3rd group has size 3, and so on.
For each group:
- If the **actual number of nodes** in that group is **even**, reverse the nodes in that group.
- If the actual number of nodes in that group is **odd**, leave the group as-is.
Note: The final group may contain fewer nodes than its intended size; its **actual length** determines whether it should be reversed.
Return the head of the modified linked list.
### Input/Output
- **Input:** `head` — head node of a singly linked list.
- **Output:** head of the updated list after performing the operations above.
### Example
List: `1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9`
- Group sizes: 1 | 2 | 3 | 4 ...
- Groups: `[1]`, `[2,3]`, `[4,5,6]`, `[7,8,9]` (last group has length 3)
- Reverse even-length groups only: `[2,3]` is even → becomes `[3,2]`; others unchanged
Result: `1 -> 3 -> 2 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9`
### Constraints (typical)
- Number of nodes `n`: `1 <= n <= 10^5`
- Node values can be any integers (do not affect the logic).
- Aim for `O(n)` time and `O(1)` extra space (excluding recursion stack).
Quick Answer: This question evaluates proficiency with singly linked list manipulation, in-place group operations (including conditional group reversal based on group length), pointer handling, and reasoning about linear time and constant extra space constraints.
You are given the head of a singly linked list, represented here as an array of its node values in order.
Traverse the list in contiguous groups of strictly increasing size: the 1st group has size 1, the 2nd group has size 2, the 3rd group has size 3, and so on.
For each group:
- If the ACTUAL number of nodes in that group is EVEN, reverse the nodes in that group.
- If the actual number of nodes is ODD, leave the group unchanged.
The final group may contain fewer nodes than its intended size; its actual length (not its intended size) determines whether it is reversed.
Return the resulting list as an array of node values.
Example:
Input: [1,2,3,4,5,6,7,8,9]
Groups: [1] | [2,3] | [4,5,6] | [7,8,9] (last group actual length 3)
Only [2,3] is even -> reversed to [3,2]; the rest are odd and unchanged.
Output: [1,3,2,4,5,6,7,8,9]
Note on signatures: although the input/output is given as an array for execution, the intended interview task operates on actual ListNode pointers in O(n) time and O(1) extra space (rewiring next pointers). The array form is purely for testing.
Constraints
- 1 <= n <= 10^5 (n = number of nodes); the test harness additionally allows the empty list for completeness.
- Node values can be any integers (including negatives); values do not affect the grouping/reversal logic.
- Target O(n) time and O(1) extra space (excluding any recursion stack).
Examples
Input: ([1, 2, 3, 4, 5, 6, 7, 8, 9],)
Expected Output: [1, 3, 2, 4, 5, 6, 7, 8, 9]
Explanation: Groups [1] | [2,3] | [4,5,6] | [7,8,9]. Only [2,3] is even (len 2) -> reversed to [3,2]. Last group length 3 is odd -> unchanged.
Input: ([5, 2, 6, 3, 9, 1, 7, 3, 8, 4],)
Expected Output: [5, 6, 2, 3, 9, 1, 4, 8, 3, 7]
Explanation: Groups [5] | [2,6] | [3,9,1] | [7,3,8,4]. [2,6] (len 2) -> [6,2]; [7,3,8,4] (len 4) -> [4,8,3,7]; odd groups unchanged.
Hints
- Track the last node of the previously finalized group with a `prev` pointer (start with a dummy head). For each group, first walk forward up to `group_size` nodes to measure the group's ACTUAL length — it may be shorter than `group_size` for the final group.
- Only the actual length matters for parity. If it's even, reverse exactly that many nodes; if odd, just advance `prev` past them.
- When reversing a sublist of length `count`, point the reversed nodes so the group's new last node connects to the first node AFTER the group. After reversing, the original first node of the group becomes the group's tail — set `prev` to it before incrementing `group_size`.