After flattening the multilevel linked list it becomes:
Problem overview
A multilevel list is a linked list in which a node may also have a child, the head of another list, and those lists can have children too. Flattening puts every node into one single-level order, where each node's child list comes immediately after that node and before the node's old next sibling.
In the lesson the structure is stored in a table adj, a slice of (i32, i32) pairs. Node ids start at 1 and double as the node values. The entry adj[id] is (next, child), with 0 meaning "no node". The function flatten(adj, head, result) pushes the flattened ids onto result.
For the example with levels 1-2-3-4-5-6, 7-8-9-10 under node 3 and 11-12 under node 8, the result is [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6]. For 1-2 with node 3 as the child of 1, it is [1, 3, 2]. An empty list gives an empty result. This time the statement asks for an iterative solution, with no recursion, in O(n) time.
Approach: replace the call stack with a vector
The recursive version records a node, flattens its child, then flattens its next. A recursive call is just "remember what is left to do, then do something else first". An explicit stack can do the same bookkeeping by hand.
Keep a Vec of ids that still have to be visited, and treat its end as the top. Repeatedly pop an id, record it, and then push the work that is now pending. Two things are pending after visiting a node: its child list, which must come first, and its next sibling, which must wait until the child list is completely done. A stack gives back the most recently pushed item first, so push next and then push child last. The child is on top, so it is popped immediately after the node, and everything under it (its own child, then its own next) is finished before the saved next comes back to the top.
Trace of 1-2 with child 3 under 1: start with [1]. Pop 1, record it, push 2, then push 3, giving [2, 3]. Pop 3 and record it. 3 has no next and no child, so nothing is pushed. Pop 2 and record it. The result is [1, 3, 2].
Each node is pushed at most once and popped once, so the time is O(n).
Step by step
- Create the stack:
let mut stack = vec![head];. It ismutbecause it will be pushed to and popped from, andvec!builds a vector from a list of elements. - Loop with
while let Some(node) = stack.pop().popreturns anOption:Some(id)while the stack has items andNonewhen it is empty, which ends the loop. - Check for a placeholder. The head is 0 when the list is empty, so an id of 0 is not a real node.
- Skip it with
continue, which jumps to the next pop without recording anything. - Record the node with
result.push(node). A node is recorded the moment it is popped, so pop order is flattened order. - Read the entry:
let (next, child) = adj[node as usize];. The slice is indexed withusize, so thei32id is cast. - Check that
nextis a real sibling before pushing, so placeholders stay off the stack. - Push
nextfirst, so that it is handled after the child. - Check that
childis a real node. - Push
childlast. It sits on top and is popped next, which puts the whole child list between the node and its next.
The solution in Rust
struct Solution;
impl Solution {
fn flatten(adj: &[(i32, i32)], head: i32, result: &mut Vec<i32>) {
let mut stack = vec![head];
while let Some(node) = stack.pop() {
if node == 0 {
continue;
}
result.push(node);
let (next, child) = adj[node as usize];
if next != 0 {
stack.push(next);
}
if child != 0 {
stack.push(child);
}
}
}
}
Rust details worth knowing:
Vecas a stack.pushadds at the end andpopremoves from the end, both in constant time. No separate stack type is needed.while letwithpop(). The loop tests for emptiness and takes the value in one step. There is no separate check ofstack.is_empty().continue. It skips the rest of the loop body for this pass. Here it is only needed for the very first element, because the two!= 0checks keep zeros off the stack afterward.- The heap holds the work list. A
Veclives on the heap and grows as needed, while the call stack of a recursive version is small and fixed. A chain of 200,000 nested children overflows the call stack in the recursive version, but this loop handles it and returns 200,000 ids. - Destructuring a pair.
let (next, child) = adj[node as usize];copies the two integers out of the slice. No borrow outlasts the statement.
Complexity
Time: O(n). Every node is pushed at most once and popped once, and each pop does constant work.
Space: O(n) including the result. The result has n ids. The stack holds at most one pending next sibling per open level, plus the child on top, so it never grows beyond the nesting depth plus one. That is far below n for most inputs, and the loop never needs the deep call stack that recursion would.
Edge cases and common mistakes
- Empty list. The stack starts as
[0]. The first pop yields 0, whichcontinueskips, and the next pop yieldsNone. The result stays empty. - Pushing child before next. The next sibling would then sit on top and come out first, so example 2 would give
[1, 2, 3]instead of[1, 3, 2]. - Skipping the zero checks. Zeros pushed onto the stack would still be skipped when popped, so the answer stays correct, but the stack does extra work. The checks keep it clean.
- Dropping the first check. An empty list has
head = 0. Without the check, the code would push 0 into the result and then readadj[0]. - Recording on push instead of on pop. The order of pushes is not the flattened order. Record when the id is popped.
- Table size.
adjneedsmax_id + 1entries because index 0 is unused.
Testing
- The three-level example gives
[1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6], withadj[3] = (4, 7)andadj[8] = (9, 11). - Node 1 with next 2 and child 3 gives
[1, 3, 2]. - The head 0 gives
[].
