#430

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Flatten a Multilevel Doubly Linked List

Flatten a multilevel doubly linked list by correctly updating next, prev, and child pointers to create a single-level sequence of nodes.

linked list depth first search doubly linked list

Problem Statement

You are given a doubly linked list where each node has next, prev, and an optional child pointer. Some nodes may point to a separate doubly linked list through the child pointer, and these child lists may themselves contain additional children, forming a multilevel structure.

Write a function to flatten the list so that all nodes appear in a single-level doubly linked list. For each node with a child, the nodes in the child list should appear immediately after that node and before its original next node. Ensure all child pointers are set to null in the final flattened list.

Examples

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 multilevel linked list in the input is shown. After flattening the multilevel linked list it becomes:

Example 2

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

Output: [1,3,2]

The multilevel linked list in the input is shown. After flattening the multilevel linked list it becomes:

Example 3

Input: head = []

Output: []

There could be empty list in the input.

Constraints

The number of Nodes will not exceed 1000.
1 <= Node.val <= 105

Solution Approach

Iterative Depth-First Traversal

Use a stack to traverse the list iteratively. Push next nodes onto the stack before diving into any child nodes, then reconnect pointers as you pop nodes from the stack. This ensures children are flattened before continuing along the original next pointers.

Recursive DFS Flattening

Implement a recursive function that flattens child lists first, then reconnects the current node with the flattened child and the original next node. Return the tail of the flattened list for proper pointer linkage. Recursive DFS simplifies pointer management but uses call stack space proportional to the depth.

Pointer Rewiring Strategy

At each node with a child, identify the child list's head and tail. Connect the current node's next to the child head and the child tail's next to the original next node. Set the child pointer to null after rewiring. This direct pointer manipulation avoids unnecessary stack usage and is optimal for interview clarity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N), where N is the total number of nodes across all levels, because each node is visited once. Space complexity is O(D) for recursive DFS due to the call stack, where D is the maximum depth of nesting, or O(N) for iterative stack-based approaches in the worst case.

What Interviewers Usually Probe

Clarify how to handle null child pointers and empty lists.
Expect you to traverse nodes in the correct flattened order using pointer manipulation.
Check that all child pointers are properly nullified and prev/next pointers remain consistent.

Common Pitfalls or Variants

Common pitfalls

Forgetting to set child pointers to null after flattening, leading to dangling references.
Misconnecting next and prev pointers when inserting child lists, which breaks the doubly linked structure.
Using inefficient repeated scans instead of a DFS approach, causing higher time complexity.

Follow-up variants

Flatten a multilevel singly linked list where each node has only next and child pointers.
Flatten a tree-like linked list with arbitrary branching instead of strict next/child structure.
Flatten and reverse a multilevel doubly linked list in one pass, maintaining depth-first order.

FAQ

What is the main pattern used in Flatten a Multilevel Doubly Linked List?

The primary pattern is linked-list pointer manipulation, often implemented with depth-first traversal to flatten child nodes correctly.

Can I flatten the list iteratively instead of recursively?

Yes, using a stack to store next nodes while processing child lists allows an iterative depth-first flattening.

Do I need to handle empty input lists?

Yes, if the head is null, the flattened result should also be null, and no pointer operations are needed.

What happens if a node has multiple nested children?

Each child is recursively flattened and inserted immediately after its parent node, maintaining depth-first order.

How should prev pointers be updated during flattening?

Prev pointers should always point to the previous node in the flattened sequence, including when connecting child list tails to original next nodes.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

"""
# 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':
        def preorder(pre, cur):
            if cur is None:
                return pre
            cur.prev = pre
            pre.next = cur

            t = cur.next
            tail = preorder(cur, cur.child)
            cur.child = None
            return preorder(tail, t)

        if head is None:
            return None
        dummy = Node(0, None, head, None)
        preorder(dummy, head)
        dummy.next.prev = None
        return dummy.next

Continue Practicing

#432 all oone data structure #460 lfu cache #146 lru cache