LeetCode 430: Flatten a Multilevel Doubly Linked List Solution in Python – A Step-by-Step Guide

What Is LeetCode 430: Flatten a Multilevel Doubly Linked List?

In LeetCode 430: Flatten a Multilevel Doubly Linked List, you’re given the head of a multilevel doubly linked list, where each Node has a value (val), a prev pointer to the previous node, a next pointer to the next node, and a child pointer to a possible sublist (or None). Your task is to flatten this structure into a single-level doubly linked list, where all nodes are connected via prev and next, and all child pointers are set to None. For example, a list starting with 1 ↔ 2 ↔ 3, where 3’s child is 7 ↔ 8 ↔ 9 (and 8’s child is 10 ↔ 11), flattens to 1 ↔ 2 ↔ 3 ↔ 7 ↔ 8 ↔ 10 ↔ 11 ↔ 9. The flattening follows the order of visiting nodes depth-first, inserting child lists between a node and its next node.

Problem Statement

• Input: A Node object (head of a multilevel doubly linked list).
• Output: A Node object (head of the flattened doubly linked list).
• Rules:
• Flatten in-place, reusing nodes.
• child pointers become None in result.
• Follow depth-first order: insert child list before next node.

Constraints

• Number of nodes is in range [0, 1000].
• 1 <= Node.val <= 10⁵.

Examples

• Input: 1 ↔ 2 ↔ 3, 3.child = 7 ↔ 8 ↔ 9, 8.child = 10 ↔ 11
• Output: 1 ↔ 2 ↔ 3 ↔ 7 ↔ 8 ↔ 10 ↔ 11 ↔ 9.
• Input: 1 ↔ 2 ↔ 3
• Output: 1 ↔ 2 ↔ 3 (no children, unchanged).
• Input: []
• Output: None.

Understanding the Problem: Flattening the List

To solve LeetCode 430: Flatten a Multilevel Doubly Linked List in Python, we need to transform a multilevel doubly linked list into a single-level one by integrating child sublists into the main list, maintaining prev and next pointers, and nullifying child pointers. A naive idea might be to collect all nodes and relink them—but we can do it in-place! We’ll use:

• Best Solution (Recursive Flattening): O(n) time, O(h) space (h = max depth)—unwinds efficiently.
• Alternative Solution (Iterative with Stack): O(n) time, O(n) space—processes with a stack.

Let’s dive into the recursive solution with a clear, step-by-step explanation.

Best Solution: Recursive Flattening

Why This Is the Best Solution

The recursive flattening method is the top pick because it’s efficient—O(n) time, O(h) space (h = maximum depth)—and elegantly handles the multilevel structure by recursively processing each node’s child list and merging it into the main list in-place. It follows a depth-first approach, flattening child sublists before linking to the next node, using minimal extra space beyond the recursion stack. It’s like unwinding a tangled thread, straightening each knot as you go!

How It Works

Think of the list as a rope with side branches you’re straightening:

• Step 1: Base Case:
• If node is None, return None (end of list).
• Step 2: Flatten Recursively:
• For current node:
• If no child, move to next (no flattening needed).
• If child exists:
• Flatten child list (get its head and tail).
• Link child head to current’s next.
• Link child tail to original next (if any).
• Set child to None.
• Recurse on new next.
• Step 3: Return Head:
• Return original head after flattening.
• Step 4: Why This Works:
• Depth-first ensures child lists are fully flattened before proceeding.
• In-place linking reuses nodes, maintaining doubly linked structure.
• It’s like ironing out each kink in the list, one branch at a time!

Step-by-Step Example

Example: 1 ↔ 2 ↔ 3, 3.child = 7 ↔ 8 ↔ 9, 8.child = 10 ↔ 11

• Initial List:

1 ↔ 2 ↔ 3 ↓ 7 ↔ 8 ↔ 9 ↓ 10 ↔ 11

• Flatten (head = 1):
• Node 1: No child, next = 2.
• Node 2: No child, next = 3.
• Node 3: Child = 7:
• Flatten 7:
• Node 7: Next = 8.
• Node 8: Child = 10:
• Flatten 10:
• Node 10: Next = 11.
• Node 11: No child, return 11.
• 10 ↔ 11, tail = 11.
• Node 8: Link 8.next = 10, 11.next = 9, 8.child = None.
• 7 ↔ 8 ↔ 10 ↔ 11 ↔ 9, tail = 9.
• Node 3: 3.next = 7, 9.next = None, 3.child = None.
• Result: 1 ↔ 2 ↔ 3 ↔ 7 ↔ 8 ↔ 10 ↔ 11 ↔ 9.

Example: 1 ↔ 2 ↔ 3

• Flatten: No children, unchanged.
• Result: 1 ↔ 2 ↔ 3.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy code# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head:
            return None

        # Step 1: Start recursion
        def flatten_helper(node):
            if not node:
                return None

            # Current node processing
            curr = node
            while curr:
                if not curr.child:
                    # No child, move to next
                    curr = curr.next
                else:
                    # Has child, flatten it
                    child_head = flatten_helper(curr.child)
                    child_tail = child_head
                    while child_tail.next:
                        child_tail = child_tail.next

                    # Link child list into main list
                    if curr.next:
                        child_tail.next = curr.next
                        curr.next.prev = child_tail
                    curr.next = child_head
                    child_head.prev = curr
                    curr.child = None

                    # Move to next after child insertion
                    curr = child_tail.next

            # Return head of flattened segment
            return node

        return flatten_helper(head)

• Line 2-7: Node class (given):
• val, prev, next, child pointers.
• Line 11-13: Handle empty list, return None.
• Line 16-39: Flatten helper:
• Line 18-19: Base case, return None if node is None.
• Line 22-37: Process current node:
• Line 23: Track current node.
• Line 24-36: While loop:
• Line 25-26: No child, move to next.
• Line 28-35: Has child:
• Recurse on child, get head (e.g., 7).
• Find child tail (e.g., 9).
• Link child tail to original next (if any).
• Link current to child head (e.g., 3 ↔ 7).
• Nullify child.
• Line 36: Move to next after child insertion.
• Line 38: Return head of flattened segment.
• Line 40: Call helper with head, return result.
• Time Complexity: O(n)—each node processed once.
• Space Complexity: O(h)—recursion stack, h = max depth.

This is like untangling a multilevel rope with a recursive iron!

Alternative Solution: Iterative with Stack

Why an Alternative Approach?

The iterative with stack method uses a stack to process nodes depth-first, flattening child lists into the main list without recursion. It’s O(n) time and O(n) space—explicit but uses more memory. It’s like stacking nodes to iron out later, one by one!

How It Works

Think of it as stacking and unstacking:

• Step 1: Push head onto stack.
• Step 2: While stack isn’t empty:
• Pop node, link to previous.
• Push children in reverse order, handle next.
• Step 3: Return head.

Step-by-Step Example

Example: 1 ↔ 2 ↔ 3, 3.child = 7 ↔ 8 ↔ 9, 8.child = 10 ↔ 11

• Stack: [1], prev = None.
• Pop 1: prev = 1, push [4, 3, 2].
• Pop 2: 1 ↔ 2, prev = 2, no kids.
• Pop 3: 1 ↔ 2 ↔ 3, prev = 3, push [7].
• Pop 7: 1 ↔ 2 ↔ 3 ↔ 7, prev = 7, push [8].
• Pop 8: 1 ↔ 2 ↔ 3 ↔ 7 ↔ 8, prev = 8, push [10].
• Pop 10: 1 ↔ 2 ↔ 3 ↔ 7 ↔ 8 ↔ 10, prev = 10, push [11].
• Pop 11: 1 ↔ 2 ↔ 3 ↔ 7 ↔ 8 ↔ 10 ↔ 11, prev = 11, push [9].
• Pop 9: 1 ↔ 2 ↔ 3 ↔ 7 ↔ 8 ↔ 10 ↔ 11 ↔ 9.
• Result: 1 ↔ 2 ↔ 3 ↔ 7 ↔ 8 ↔ 10 ↔ 11 ↔ 9.

Code for Iterative Approach

Copy codeclass Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head:
            return None

        stack = [head]
        prev = None

        while stack:
            node = stack.pop()
            if prev:
                prev.next = node
                node.prev = prev

            # Push next first (processed last)
            if node.next:
                stack.append(node.next)
            # Push children in reverse order
            for child in reversed(node.children):
                stack.append(child)
            node.child = None
            prev = node

        return head

• Time Complexity: O(n)—each node processed once.
• Space Complexity: O(n)—stack holds all nodes.

It’s a stack-driven flattener!

Comparing the Two Solutions

• Recursive Flattening (Best):
• Pros: O(n), O(h), elegant and lean.
• Cons: Recursion stack.
• Iterative with Stack (Alternative):
• Pros: O(n), O(n), explicit control.
• Cons: More memory.

Recursive wins for space efficiency.

Additional Examples and Edge Cases

• []: None.
• [1]: 1.
• [1,2,3]: 1 ↔ 2 ↔ 3.

Recursive handles all.

Complexity Breakdown

• Recursive: Time O(n), Space O(h).
• Iterative: Time O(n), Space O(n).

Recursive is optimal.

Key Takeaways

• Recursive: Unwind smart!
• Iterative: Stack it up!
• Lists: Links twist.
• Python Tip: Pointers rock—see [Python Basics](/python/basics).

Final Thoughts: Flatten That List

LeetCode 430: Flatten a Multilevel Doubly Linked List in Python is a list-straightening quest. Recursive flattening unwinds it fast, while iterative stacking processes it steady. Want more list fun? Try LeetCode 114: Flatten Binary Tree to Linked List or LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List. Ready to flatten? Head to Solve LeetCode 430 on LeetCode and straighten that list today!