1032. Flatten the Folder Chain
A file explorer lists folders as a doubly linked list using prev and next. A folder may also have a child pointer to the head of its own sub-list, and nodes in that sub-list can have children too. Given head, flatten everything into one single-level list: the whole sub-list of a folder must appear right after that folder and before the folder's old next, recursively.
Afterwards every child must be null and all prev/next links must be consistent. Return the head of the flattened list (null for an empty list). Aim for O(n) time over all nodes; avoid recursion since nesting can be 100000 levels deep.
Example 1
- Input:
- head = [1,[2,[3,4]],5]
- Output:
- [1,2,3,4,5]
- Explanation:
Node 2 has a child list 3, 4, which is spliced in right after 2, giving 1, 2, 3, 4, 5.
Example 2
- Input:
- head = [[7,[[3,[9,1]],4]],8]
- Output:
- [7,3,9,1,4,8]
- Explanation:
Node 7 owns the list 3, 4 where 3 owns 9, 1; the order is 7, then 3 with its sub-list 9, 1, then 4, then 8.
Constraints
0 ≤ total number of nodes n ≤ 105
-104 ≤ node value ≤ 104
The structure is a tree of lists: no node is reachable twice.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)