Practice/Amazon/Leetcode 430. Flatten a Multilevel Doubly Linked List

Leetcode 430. Flatten a Multilevel Doubly Linked List

CodingMust

Problem

You are given a doubly linked list where each node has the standard prev and next pointers, but also includes a child pointer that may point to a separate doubly linked list. These child lists may also have their own child pointers, creating a multi-level data structure.

Your task is to flatten this multi-level doubly linked list so that all nodes appear in a single-level doubly linked list. The flattening should follow these rules:

• When you encounter a node with a child pointer, the entire child list should be inserted between that node and its next node
• Child lists should be flattened before continuing with the parent level
• After flattening, all child pointers should be set to null
• The prev and next pointers should be properly maintained in the flattened list

Requirements

1. Return the head of the flattened list
2. Maintain proper doubly linked list structure (both prev and next pointers must be correct)
3. Set all child pointers to null after flattening
4. Process child lists depth-first (fully flatten a child list before moving to the next node at the current level)

Constraints

• The number of nodes in the list is in the range [0, 1000]
• Node values are integers
• 1 ≤ Node.val ≤ 10^5
• The depth of the multi-level structure will not exceed 1000
• Time complexity should be O(n) where n is the total number of nodes
• Space complexity should be O(d) where d is the maximum depth (recursion stack or explicit stack)

Examples

Example 1:

` Input: 1---2---3 | 7---8

Output: 1---7---8---2---3

Explanation: Starting at node 1, we find it has a child (7). We insert the child list (7->8) between node 1 and node 2, resulting in 1->7->8->2->3. `

Example 2:

` Input: 1---2---3---4 | | 5---6 9---10 | 7---8

Output: 1---5---6---7---8---2---3---9---10---4

Explanation:

• Node 1 has child 5->6
• Node 6 has child 7->8
• We flatten 1's child completely first (including 6's child), getting 5->6->7->8
• Then we continue with 2->3
• Node 3 has child 9->10, which gets inserted
• Final result: 1->5->6->7->8->2->3->9->10->4 `

Example 3:

` Input: null Output: null

Explanation: An empty list returns null. `