Flatten a Multilevel Doubly Linked List
Medium · Linked Lists · Linked List · Depth-First Search · Doubly-Linked List
Problem
You are given the head of a doubly linked list whose nodes have next, prev and an extra child pointer. A child pointer, when set, leads to a separate doubly linked list, whose nodes may have children of their own, forming several levels.
Flatten everything into one single-level doubly linked list, using the nodes you were given. Whenever a node has a child list, that entire child list (already flattened) goes right after the node and before the node’s original next. In the result, every child pointer must be None and every prev must point to the node before it. Return the head.
In the examples, head is written as a nested list: values are the nodes of one level, left to right, and a list right after a value is that node’s child list. The output lists the flattened values in order.
Examples
Input: head = [1,2,[4,5],3] Output: [1,2,4,5,3]
Node 2 owns the child list 4 5, which is spliced in between 2 and 3.
Input: head = [1,[3,4,[5]],2] Output: [1,3,4,5,2]
Node 1 owns 3 4 and node 4 owns 5, so the child lists are expanded depth first.
Input: head = [] Output: []
An empty list stays empty.
Constraints
- 0 <= total number of nodes <= 1000
- 1 <= Node.val <= 10^5
- At most 100 levels
Approaches
- Baseline: collect the nodes in order, then relink — time O(n), space O(n)
Follow-up
Can you do it without recursion or a stack? Splicing each child level in place and walking on does it in O(1) extra space. See the use cases for listing the levels breadth-first instead, and for a sum weighted by each node’s level.
Related problems
Start free on Cariara · Coding problems · System design studio
