Coding Interview PatternsFlatten a Multilevel Doubly Linked List
MediumFast and Slow Pointers

Flatten a Multilevel Doubly Linked List

Explanation & Solution

Practice Problem

Description

You are given the head of a multilevel doubly linked list. In this list, nodes may have a child pointer to a separate doubly linked list. These child lists may themselves have children, forming multiple levels.

Flatten the list so that all nodes appear in a single-level doubly linked list. The nodes should appear in depth-first order (DFS) — when a node has a child, the child sublist is inserted between the node and its next sibling.

The input is encoded as a flat array using the LeetCode convention: non-null values are node values in order; a sequence of null values separates levels. The number of nulls before a child group indicates the 0-indexed position (minus 1) within the parent group where the child attaches.

Return the flattened list as an array of values in DFS order.

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

Explanation:

  • Level 1: 1→2→3→4→5→6
  • Node 3 (index 2) has child → Level 2: 7→8
  • Node 8 (index 1 in its group) has child → Level 3: 11→12
  • DFS order: 1, 2, 3, 7, 8, 11, 12, 4, 5, 6

Constraints

  • The number of nodes in the list is in the range [0, 1000]
  • 1 <= Node.val <= 10⁶
  • The depth of the multilevel list is at most 1000

Approach

Fast and Slow Pointers pattern

1. Parse the Input into Segments

  • Walk through the flat array, grouping consecutive non-null values into segments
  • Track the number of null values between each pair of segments in a gaps array
  • For example, [1,2,3,4,5,6,null,null,null,7,8] produces segments [[1,2,3,4,5,6], [7,8]] and gaps = [3]

2. Build the Parent-Child Relationships

  • The null count between segment i and segment i+1 encodes where the child attaches
  • Specifically, segment i+1 is a child of the node at index gaps[i] - 1 within segment i
  • For 3 nulls between [1,2,3,4,5,6] and [7,8], the child attaches at index 2 (node with value 3)

3. DFS Traversal

  • Start DFS at segment 0 (the main list)
  • For each node in the segment, add its value to the result
  • If the current node has a child segment, recursively DFS into that child segment before continuing with the next sibling
  • This produces the correct depth-first flattened order

4. Return the Result

  • The result array now contains all node values in DFS order
  • This matches the order you would get by flattening the multilevel structure in-place

🧠 Key Insight

  • The core algorithm for flattening a multilevel list is a stack-based DFS (or recursion): when you encounter a child, push the remaining siblings onto a stack and process the child first
  • In an actual linked list implementation, you would rewire next/prev pointers and clear child pointers
  • The null-count encoding is a compact serialization: each null group acts as a positional marker for where the child attaches
Time
O(n) where n is the total number of nodes
Space
O(d) where d is the maximum depth of nesting (recursion stack)

Visualization

Input:
Linked List Traversal
—
10213243546567879810111211131214null

No animation available

Slow (S)Fast (F)Both
0 steps

Solution Code

Previous
Add Two Numbers II
Next
Copy List with Random Pointer