40. Flatten a Multilevel Doubly Linked List

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

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