MediumLinked ListDoubly-Linked ListDepth-First Search

Flatten a Multilevel Doubly Linked List

1 approach, code in every language

You are given a doubly linked list in which each node has the usual previous and next pointers, but may also carry a child pointer that leads to a separate doubly linked list. That child list can itself contain nodes with their own children, producing an arbitrarily deep multilevel structure.

Flatten the whole structure into a single-level doubly linked list. When a node has a child, its child list should be spliced in immediately after that node and before whatever originally followed it, mirroring a depth-first traversal. After flattening, every node's child pointer must be null, and the prev and next pointers must correctly describe the single-level list. Return the head of the flattened list.

Example 1

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

Output: [1,2,3,7,8,11,12,9,10,4,5,6]

The child list hanging off node 3 is inserted right after it, and that list's own child off node 8 is inserted after 8, all before the traversal returns to node 4.

Example 2

Input: head = [1,2,null,3]

Output: [1,3,2]

Node 1 has a child list starting at 3, so 3 is spliced between 1 and 2, and the child pointer is cleared.

Constraints

The number of nodes is in the range [0, 1000].
1 <= Node.val <= 10^5

Depth-First Recursion

Walk the current level; whenever a node has a child, recursively flatten that child list and splice it between the node and its successor.

Loading animation…

Intuition

Flattening in depth-first order means that as soon as we meet a node with a child, the entire child list, fully flattened, must appear before we continue along the current level. We process one level with a loop, and whenever the current node owns a child we recurse to flatten that sublevel first. The recursive call returns the tail of the flattened child list, which is exactly the node we must connect back to the original successor. We rewire next and prev pointers on both the join between the node and its child head and the join between the child tail and the saved successor, then clear the child pointer. Returning the last node of a flattened level lets each parent frame stitch its sublist back together in constant time.

Algorithm walkthrough

1If the head is null, return it directly since there is nothing to flatten.
2Use a helper that scans the current level with a pointer, remembering next = curr.next before any rewiring.
3When curr has a child, recursively flatten the child to obtain its tail, then set curr.next to the child head and the child head's prev back to curr, and clear curr.child.
4If a saved next existed, connect the child tail to it by setting childTail.next = next and next.prev = childTail so the level continues after the inserted block.
5Track the last node visited and return it so parent calls can splice, then finally return the original head.

Implementation

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

        def dfs(node):
            curr = node
            last = node
            while curr:
                nxt = curr.next
                if curr.child:
                    child_tail = dfs(curr.child)
                    curr.next = curr.child
                    curr.child.prev = curr
                    curr.child = None
                    if nxt:
                        child_tail.next = nxt
                        nxt.prev = child_tail
                    last = child_tail
                else:
                    last = curr
                curr = nxt
            return last

        dfs(head)
        return head

Time

O(n)

Space

O(n)

Each node is touched once. The recursion depth equals the nesting depth of children, which is O(n) in the worst case.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free