Flatten a Multilevel Doubly Linked List: DFS Pointer Manipulation

You are given a doubly linked list where each node has three pointers: next, prev, and child. The child pointer may point to a separate doubly linked list, which itself can have nodes with child pointers, creating multiple levels of nesting. Your task is to flatten this structure into a single-level doubly linked list. When a node has a child list, that child list should be inserted between the node and its original next neighbor.

This is LeetCode 430: Flatten a Multilevel Doubly Linked List, and it is a great test of whether you can do precise pointer manipulation without losing track of nodes.

Why this problem matters

Flattening a multilevel linked list combines two skills that show up constantly in interviews: depth-first traversal and pointer rewiring. You need to handle the child lists in a DFS-like order (go deeper before continuing forward), and you need to stitch pointers without orphaning any part of the list.

This same pattern appears in tree flattening problems like Flatten Binary Tree to Linked List, where you transform a hierarchical structure into a linear one. The difference here is that you are working with doubly linked pointers, so you need to maintain both next and prev connections. If you forget to update prev, you end up with a list that works going forward but breaks going backward.

The problem also teaches you a reusable trick: when you need to splice a sublist into a linked list, save the next pointer, connect the sublist, walk to the sublist's tail, then reconnect to the saved node. You will use this technique in many linked list problems.

The approach

The iterative approach walks through the list node by node. When you encounter a node with a child pointer, you do three things:

1. Find the tail of the child list by walking to its end.
2. Connect the child list's tail to the current node's next neighbor.
3. Connect the current node to the child list's head, and clear the child pointer.

Then you continue walking forward. Because the child list is now part of the main list, any nested children within it will be handled naturally as you keep iterating.

def flatten(head):
    if not head:
        return head

    curr = head
    while curr:
        if curr.child:
            child_head = curr.child
            child_tail = child_head
            while child_tail.next:
                child_tail = child_tail.next

            child_tail.next = curr.next
            if curr.next:
                curr.next.prev = child_tail

            curr.next = child_head
            child_head.prev = curr
            curr.child = None

        curr = curr.next

    return head

The key detail is that we find the child_tail before doing any rewiring. This guarantees we have a handle on the end of the child list so we can connect it to whatever comes after the current node. If curr.next is None (the current node is the last node), we just leave child_tail.next as None, which is already correct.

Notice that we also set curr.child = None after splicing. The problem requires all child pointers to be null in the final result.

Step-by-step walkthrough

Let's trace the algorithm on a list where Level 1 is 1 <-> 2 <-> 3 <-> 4 and node 2 has a child list 5 <-> 6.

The algorithm handles deeper nesting naturally. If node 5 also had a child list, it would get spliced in when curr reaches node 5 during the iteration. Because the child list is inserted right after the current node, any children within it are guaranteed to be processed before we reach the original next node.

Complexity analysis

Time: We visit every node exactly once as curr, plus we walk each child list once to find its tail. Since every node belongs to exactly one child list (or the top level), the total work across all tail-finding walks is O(n). Each node is visited at most twice total.

Space: We use a constant number of pointer variables (curr, child_head, child_tail). No stack, no recursion, no hash map. True O(1) extra space.

Edge cases to watch for

• Empty list (head is None): return None immediately.
• Single node with no child: already flat. Return it as-is.
• Single node with a child list: the child list becomes the entire rest of the flat list.
• Deeply nested children (child of child of child): the algorithm handles this naturally. Each child list gets spliced in before we reach its parent's next, so deeper levels are flattened first.
• Child list at the last node: curr.next is None, so we skip the curr.next.prev = child_tail assignment. The child list becomes the new tail of the flat list.
• All nodes have children: every node triggers splicing. The algorithm still runs in O(n) time because each node is visited at most twice.

The building blocks

This problem combines two reusable patterns:

Linked list splicing. The core operation is inserting a sublist between two nodes. Save the next pointer, connect the head of the sublist, walk to its tail, then connect the tail to the saved node. This same technique appears in Reverse Linked List (where you splice reversed segments) and any problem that requires inserting or moving chunks of a linked list.

DFS-order processing. By iterating forward through the list and splicing child lists inline, we process nodes in a depth-first order. When we hit a child, we go "deeper" by inserting the child list right here. This is the same traversal order you see in Flatten Binary Tree to Linked List, just expressed iteratively through pointer manipulation instead of recursion.

From understanding to recall

You have seen the algorithm, traced it step by step, and understand why each pointer assignment is necessary. But the details are where interviews get tricky. Do you remember to find the child tail before rewiring? Do you remember to set child.prev = curr? Do you remember to clear curr.child?

These are not conceptual gaps. They are recall gaps. You understand the logic, but under time pressure, one missed prev pointer means your solution breaks on the backward traversal.

Spaced repetition closes that gap. You write the solution from memory at increasing intervals until the pointer sequence becomes automatic. When a linked list flattening problem appears, you do not pause to rederive it. You just write it.

Related posts

• Flatten Binary Tree to Linked List - The tree version of the same flattening pattern, transforming a hierarchical structure into a linear one
• Reverse Linked List - The foundational linked list pointer manipulation problem
• Copy List with Random Pointer - Another linked list problem with extra pointers that require careful handling