40. Flatten a Multilevel Doubly Linked List

40. Flatten a Multilevel Doubly Linked List

Medium
48.0%
1.4k
dfslinked-liststackrecursion
Google, Amazon, Netflix, Meta (Facebook), Apple, Microsoft, Uber, Bloomberg, Airbnb, Stripe, Adobe, Salesforce, LinkedIn, Oracle

You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:

A large-scale platform stores hierarchical data such as:

  • nested comments in a discussion thread
  • multi-level task breakdowns
  • category trees with ordered siblings
  • UI navigation items with expandable groups

To optimize rendering and caching, the platform uses a multilevel doubly linked list where:

  • next and prev define the normal order of items on the same level
  • child points to another doubly linked list representing nested items

Before sending data to a client or writing to a flat storage format, the platform needs to flatten this structure into a single-level doubly linked list that preserves the depth-first order.

This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.

Your Task

Given the head of a multilevel doubly linked list, flatten the list so that:

  • All nodes appear in a single-level doubly linked list
  • The order follows a depth-first traversal
  • All child pointers are set to null
  • prev and next pointers are updated correctly

Return the head of the flattened list.

Input Format

  • head: the head of a multilevel doubly linked list

Each node is defined as:

Node { int val; Node prev; Node next; Node child; }

Output Format

  • Return the head of the flattened doubly linked 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]
Explanation: Depth-first flattening expands node 3’s child list first, and node 8’s child list inside that.

Example 2:

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

Example 3:

Input: head = []
Output: []

Constraints

  • 0 <= number of nodes <= 10,000
  • 1 <= Node.val <= 100,000
  • The number of levels does not exceed 50
  • child may be null or point to another doubly linked list

Loading editor...

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

Console Output

Click "Run Code" or "Submit" to see results

Your code will be evaluated by AI with instant feedback