1616. Reversed Child Flatten
A folder browser keeps its entries in a multilevel doubly linked list: each node has next, prev and child, and a child points to the head of a sub-list. Write reversedChildFlatten(head) to flatten it depth-first with one twist: the top-level list keeps its order, but every child level is walked from its last node to its first. Each node is still followed immediately by its own flattened descendants, and then comes the next node on that level. Set every child to null, fix all prev links and return the head (null if empty). Test inputs put a child list in brackets after its parent, like [1,2,[3,[7,8]],4]. There are 0 to 1000 nodes and depth at most 50. Aim for O(n) time.
Example 1
- Input:
- head = [[1,[2,3]],4]
- Output:
- [1,3,2,4]
- Explanation:
Top level is 1 and 4; the child list 2, 3 of node 1 follows.
Example 2
- Input:
- head = [10,[20,[[30,[50,60]],40]],70]
- Output:
- [10,20,40,30,60,50,70]
- Explanation:
Three levels deep, with a child list hanging from a child node.
Example 3
- Input:
- head = [5,6,7]
- Output:
- [5,6,7]
- Explanation:
No node has a child, so the list is already flat.
Constraints
0 ≤ total nodes ≤ 1000
depth ≤ 50
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)