LeetCode 430 - Flatten a Multilevel Doubly Linked List

LeetCode Problem 430

Difficulty: 🟡 Medium
Topics: Linked List, Depth-First Search, Doubly-Linked List

Solution

Problem Understanding

The problem gives us a special type of doubly linked list where every node contains four fields:

val
prev
next
child

The next and prev pointers behave exactly like a normal doubly linked list. The extra child pointer introduces another linked list that branches downward from the current node. That child list can itself contain nodes with their own child pointers, creating a recursive multilevel structure.

The task is to transform this multilevel structure into a single flattened doubly linked list. The flattening order follows a depth-first traversal pattern. Whenever a node has a child list, that entire child list must be inserted immediately after the current node and before the node that originally came next.

For example, suppose node 3 has a child list starting at 7:

1 - 2 - 3 - 4
        |
        7 - 8

After flattening, the list becomes:

1 - 2 - 3 - 7 - 8 - 4

The important detail is that the original ordering must still be preserved. The child list is inserted in place, not appended at the end.

The output must remain a valid doubly linked list. That means:

• Every next pointer must be correct
• Every prev pointer must be correct
• Every child pointer must be set to null

The constraints tell us that the total number of nodes is at most 1000. This is small enough that even recursive solutions are safe in practice, although iterative approaches are also completely reasonable. Since the structure is pointer-based rather than array-based, the main challenge is correctly rewiring pointers without losing parts of the list.

Several edge cases are important:

• The input may be empty
• A node may have no child
• Multiple levels of nesting may exist
• A child list may itself contain children
• The tail of a child list must reconnect correctly to the original next node
• Every child pointer must eventually become null

A naive implementation can easily lose references to parts of the list if it overwrites pointers before saving them.

Approaches

Brute-Force Approach

A straightforward brute-force strategy is to repeatedly scan the list looking for nodes with child pointers. Whenever such a node is found, we splice the child list into the main list, then continue scanning until no child pointers remain.

The algorithm works because every iteration reduces the number of remaining child pointers. Eventually the structure becomes fully flattened.

However, this approach is inefficient because the list may be rescanned many times. In deeply nested structures, the same nodes are visited repeatedly. Pointer manipulation also becomes cumbersome because reconnecting tails requires additional traversal work.

Although the constraints are relatively small, this repeated scanning introduces unnecessary overhead.

Optimal Approach

The key insight is that flattening naturally follows a depth-first traversal.

When we encounter a node with a child:

1. Save the original next node
2. Flatten the child list recursively
3. Insert the flattened child list immediately after the current node
4. Connect the tail of the child list back to the saved next node

This works because a child list must appear completely before the original next node in the flattened ordering.

A recursive depth-first search is especially clean here because each recursive call can return the tail of the flattened sublist. That tail is exactly what we need to reconnect the remaining nodes.

Instead of rescanning portions of the list repeatedly, every node is processed once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans the list to locate and splice child lists
Optimal	O(n)	O(n)	DFS flattening processes each node once

Algorithm Walkthrough

Optimal DFS Algorithm

1. Start from the head of the list and traverse node by node.

We process the list in normal left-to-right order using the next pointer. 2. For each node, first save its original next pointer.

This step is critical because once we attach the child list, the original next reference would otherwise be lost. 3. If the current node does not have a child, simply continue forward.

No structural modification is needed in this case. 4. If the current node has a child list, recursively flatten that child list.

The recursive call returns the tail node of the flattened child portion. This is important because we later need to reconnect the original next node after the child chain ends. 5. Insert the child list between the current node and the original next.

The connections become:

current.next = child_head
child_head.prev = current

6. Remove the child pointer.

The problem explicitly requires every child pointer to become null. 7. Connect the tail of the flattened child list back to the saved next node.

If the original next node exists:

child_tail.next = next_node
next_node.prev = child_tail

8. Continue traversal from the saved next node.

This ensures the entire structure is processed in depth-first order. 9. Return the tail node of the flattened segment.

Returning the tail allows parent recursive calls to reconnect lists efficiently without rescanning.

Why it works

The algorithm maintains an important invariant:

At every recursive return, the sublist starting from the current node is completely flattened and correctly connected.

Because each child list is fully flattened before reconnecting the original next node, the final ordering exactly matches the required depth-first traversal order. Every node is visited once, and every pointer is updated consistently.

Python Solution

"""
# 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
"""

from typing import Optional

class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':

        def dfs(node: 'Optional[Node]') -> 'Optional[Node]':
            current = node
            last = node

            while current:
                next_node = current.next

                if current.child:
                    child_head = current.child
                    child_tail = dfs(child_head)

                    current.next = child_head
                    child_head.prev = current
                    current.child = None

                    if next_node:
                        child_tail.next = next_node
                        next_node.prev = child_tail

                    last = child_tail
                else:
                    last = current

                current = next_node

            return last

        if not head:
            return None

        dfs(head)
        return head

The implementation uses a helper DFS function that recursively flattens a sublist and returns its tail node.

The variable current traverses the current level of the list. Before modifying pointers, the code stores current.next inside next_node. This prevents losing access to the remaining portion of the list after inserting the child chain.

When a child exists, the algorithm recursively flattens that child sublist. The returned child_tail is then used to reconnect the original next node.

The child list is inserted immediately after the current node:

current.next = child_head
child_head.prev = current

The child pointer is then cleared:

current.child = None

Finally, if the original next node existed, the flattened child tail reconnects to it.

The helper returns the tail of the fully flattened section so higher recursive levels can reconnect correctly without additional traversal.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Prev *Node
 *     Next *Node
 *     Child *Node
 * }
 */

func flatten(root *Node) *Node {
	if root == nil {
		return nil
	}

	var dfs func(node *Node) *Node

	dfs = func(node *Node) *Node {
		current := node
		last := node

		for current != nil {
			nextNode := current.Next

			if current.Child != nil {
				childHead := current.Child
				childTail := dfs(childHead)

				current.Next = childHead
				childHead.Prev = current
				current.Child = nil

				if nextNode != nil {
					childTail.Next = nextNode
					nextNode.Prev = childTail
				}

				last = childTail
			} else {
				last = current
			}

			current = nextNode
		}

		return last
	}

	dfs(root)
	return root
}

The Go implementation closely mirrors the Python version. The main difference is explicit pointer handling with nil checks instead of Python's None.

Go also requires defining the recursive DFS function using a variable declaration before assignment:

var dfs func(node *Node) *Node

Since the constraints are small, recursion depth is safe.

Worked Examples

Example 1

Input:

1 - 2 - 3 - 4 - 5 - 6
            |
            7 - 8 - 9 - 10
                |
                11 - 12

Step-by-step traversal

Current Node	Action	Result
1	No child	Move to 2
2	No child	Move to 3
3	Has child 7	Save next node 4
7	No child	Move to 8
8	Has child 11	Save next node 9
11	No child	Move to 12
12	No child	Return tail 12
8	Attach 11-12 between 8 and 9	List partially flattened
9	No child	Move to 10
10	No child	Return tail 10
3	Attach 7-8-11-12-9-10 between 3 and 4	Main list updated
4	No child	Move to 5
5	No child	Move to 6
6	No child	Done

Final flattened list:

1 - 2 - 3 - 7 - 8 - 11 - 12 - 9 - 10 - 4 - 5 - 6

Example 2

Input:

1 - 2
    |
    3

Step-by-step traversal

Current Node	Action	Result
1	No child	Move to 2
2	Has child 3	Save next as null
3	No child	Return tail 3
2	Attach child after 2	Flatten complete

Final list:

1 - 2 - 3

The serialized output becomes:

[1,3,2]

because the flattening inserts child nodes immediately after the parent.

Example 3

Input:

[]

Since the head is None, the function immediately returns None.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(n)	Recursive call stack in worst-case nesting

The algorithm performs constant-time pointer updates per node, so total work scales linearly with the number of nodes.

The recursive DFS introduces stack usage proportional to the maximum nesting depth. In the worst case, where every node contains a child and no next node, recursion depth can become O(n).

Test Cases

# Helper Node class
class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

def list_values(head):
    result = []

    while head:
        result.append(head.val)

        # verify child pointers removed
        assert head.child is None

        head = head.next

    return result

# Example 1
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
n6 = Node(6)

n7 = Node(7)
n8 = Node(8)
n9 = Node(9)
n10 = Node(10)

n11 = Node(11)
n12 = Node(12)

n1.next = n2
n2.prev = n1
n2.next = n3
n3.prev = n2
n3.next = n4
n4.prev = n3
n4.next = n5
n5.prev = n4
n5.next = n6
n6.prev = n5

n3.child = n7

n7.next = n8
n8.prev = n7
n8.next = n9
n9.prev = n8
n9.next = n10
n10.prev = n9

n8.child = n11

n11.next = n12
n12.prev = n11

head = Solution().flatten(n1)

assert list_values(head) == [1,2,3,7,8,11,12,9,10,4,5,6]  # nested child lists

# Example 2
a = Node(1)
b = Node(2)
c = Node(3)

a.next = b
b.prev = a
b.child = c

head = Solution().flatten(a)

assert list_values(head) == [1,2,3]  # single child insertion

# Example 3
assert Solution().flatten(None) is None  # empty list

# Single node
single = Node(1)

head = Solution().flatten(single)

assert list_values(head) == [1]  # minimal input

# Deep nesting
x1 = Node(1)
x2 = Node(2)
x3 = Node(3)

x1.child = x2
x2.child = x3

head = Solution().flatten(x1)

assert list_values(head) == [1,2,3]  # recursive depth handling

# Child at tail
p1 = Node(1)
p2 = Node(2)
p3 = Node(3)

p1.next = p2
p2.prev = p1
p2.child = p3

head = Solution().flatten(p1)

assert list_values(head) == [1,2,3]  # reconnect when next is None

Test	Why
Empty list	Validates null input handling
Single node	Ensures trivial structure works
One child list	Tests basic splicing logic
Nested child lists	Validates recursive flattening
Deep nesting	Tests recursive depth correctness
Child at tail	Ensures reconnection logic works when next is null

Edge Cases

Empty input list

The input head may be None. This is the simplest edge case, but forgetting to handle it can immediately cause null pointer errors during traversal.

The implementation checks this at the beginning:

if not head:
    return None

This guarantees safe behavior before any recursive processing starts.

Child list at the tail

A node near the end of the list may contain a child while its next pointer is already null.

For example:

1 - 2
    |
    3

In this case, after flattening the child list, there is no original next node to reconnect. Incorrect implementations may accidentally dereference a null pointer or create invalid links.

The solution safely checks:

if next_node:

before reconnecting pointers.

Multiple levels of nesting

A child node may itself contain another child list several levels deep.

For example:

1
|
2
|
3

A shallow flattening strategy that only handles one level would fail here.

The recursive DFS ensures that every child list is fully flattened before reconnecting to the parent chain. Because each recursive call completely processes its subtree, arbitrary nesting depth is handled correctly.