Skip to content

430.flatten-a-multilevel-doubly-linked-list.md

Latest commit

 

History

History
250 lines (209 loc) · 6.31 KB

430.flatten-a-multilevel-doubly-linked-list.md

File metadata and controls

250 lines (209 loc) · 6.31 KB

430. Flatten a Multilevel Doubly Linked List

Hints

  1. Think about how this problem is similar to flattening a tree
  2. What traversal order would help you process nodes in the correct sequence?
  3. Consider how to handle the connections between different levels

Breakdowns

  1. First, understand what "flattening" means:

    • All nodes should be in a single level
    • Child pointers should be nullified
    • Nodes from child lists should be inserted between current node and next node

  2. For each node:

    • Process current node
    • Handle its child list (if exists)
    • Handle its next node
    • Fix all prev/next pointers

Key Insights

For each root, when flattening:

  • child is flattened first.
  • Then the flattened child list should come before next.

Idea!! It's like a tree preorder traversal, we just relink the nodes during traversal.

Example visualization:

1 -> 5 -> ...
|
2 -> 3 -> 4

flatten(1) = 1 -> 2 -> 3 -> 4 -> 5 -> ...

Recursive

The key idea is to use DFS to process nodes in preorder fashion, where we flatten child list first before connecting it with the next nodes.

current -> next
   |
 child -> ...
   |
  ...

// Start flattening from current node.
current -> f(next)
   |
 f(child) -> ...
   |
  ...

flatten(current) =
current -> f(child) -> f(next)

// And so on...

// Example:
2 -> 3
|
5 -> 6
|
7 -> 8 -> 9

f(2) =
2 -> f(5) -> f(3)

f(5) =
5 -> f(7) -> f(6)

// Backtracking...
f(7) = 7 -> 8 -> 9
f(5) = 5 -> 7 -> 8 -> 9 -> f(6)
fun flatten(root: Node?): Node? {
    if (root == null) return null
    val next = root.next
    val prev = root.prev
    val child = root.child

    val flattenedNext = flatten(next)
    if (child != null) {
        val flattenedChild = flatten(child)
        root?.child = null

        // Connect the last node of the child list to the next node.
        // See f(5) = 5 -> 7 -> 8 -> 9 -> 6, we need to connect 9 to 6.
        var last = flattenedChild
        while (last?.next != null) {
            last = last.next
        }
        last?.next = flattenedNext
        flattenedNext?.prev = last

        root.next = flattenedChild
        flattenedChild?.prev = root
    }
    return root
}
  • Time Complexity: O(N) where N is the total number of nodes
  • Space Complexity: O(H) where H is the maximum depth of the multilevel structure (recursion stack)

Iterative

The key idea is to use a stack to simulate the recursive process, pushing next and child nodes in reverse order to maintain proper sequence.

迭代就是一層一層移上來，節點有 child 就先往 stack 送，等遍歷完子節點後再從棧取出回朔。

fun flatten(root: Node?): Node? {
    if (root == null) return null
    val sentinel = Node(-1)
    var current = sentinel
    val stack = Stack<Node>()
    stack.push(root)
    while (stack.isNotEmpty()) {
        val node = stack.pop()
        current.next = node
        node.prev = current

        if (node.next != null) {
            stack.push(node.next)
        }
        if (node.child != null) {
            stack.push(node.child)
            node.child = null
        }
        current = current.next!!
    }
    /**
     * Remember to remove the sentinel node.
     * The real `prev` of the first node should be null, but we 
     * will update it while iterating:
     * ```
     * current.next = node
     * node.prev = current
     * ```
     * After flattening, the list looks like:
     * `sentinel <- -> flattened list`
     * so we have to "reset" it.
     */
    sentinel.next?.prev = null
    return sentinel.next
}
  • Time Complexity: O(N) where N is the total number of nodes
  • Space Complexity: O(N) in worst case when all nodes are in child lists

In-place

The key idea is to flatten one child level by level, and then connect it with the next level.

current -> next -> ...
    |
 child 1 -> next 1 -> ... tail 1
    |
 child 2 -> next 2 -> ... tail 2

// Flatten child 1
current -> child 1 -> next 1 ->  ... tail 1 -> next -> ...
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ // child 1 is flattened
             |
           child 2 -> next 2 -> ... tail 2

// We move `current` to `current.next`, which is `child 1`:
current -> child 1 (new current) -> ...
             |
           child 2 -> next 2 -> ... tail 2

// Flatten child 2
current -> child 1  -> child 2 -> next 2 -> ... tail 2 -> next 1 -> ... tail 1 -> next -> ...
                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ // child 2 is flattened
fun flatten(root: Node?): Node? {
    var current = root
    while (current != null) {
        if (current.child != null) {
            val next = current.next

            val child = current.child!!
            current.next = child
            child.prev = current
            current.child = null

            var tail = current!!
            while (tail.next != null) {
                tail = tail.next!!
            }

            tail.next = next
            next?.prev = tail
        }
        // current.next is the new node after flattening, which is the child node if it exists or the next node otherwise.
        current = current.next
    }
    return root
}
  • Time Complexity: O(N) where N is the total number of nodes
  • Space Complexity: O(1)

Edge Cases

  1. Single node with no child
  2. Node with child but no next
  3. Node with both child and next
  4. Multiple levels of children

Visual examples for tricky edge cases:

// Case 2: Node with child but no next
1
|
2 -> 3
     |
     4
// Should become: 1 -> 2 -> 3 -> 4

// Case 3: Node with both child and next
1 -> 2 -> 3
|
4 -> 5
     |
     6
// Should become: 1 -> 4 -> 5 -> 6 -> 2 -> 3

// Case 4: Multiple levels of children
1 -> 2
|
3
|
4 -> 5
     |
     6
// Should become: 1 -> 3 -> 4 -> 5 -> 6 -> 2

Pitfalls

  1. Forgetting to nullify child pointers after flattening
  2. Not properly handling prev pointers when connecting lists

Similar or Follow-up Problems