# 430. Flatten a Multilevel Doubly Linked List

--

Leetcode #: 430
Name: Flatten a Multilevel Doubly Linked List
Difficulty: Medium

# Prompt

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

Given the `head` of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let `curr` be a node with a child list. The nodes in the child list should appear after `curr` and before `curr.next` in the flattened list.

Return the `head` of the flattened list. The nodes in the list must have all of their child pointers set to `null`.

Example

Constraints

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

# Approach

We can use the following example that they provide to demonstrate what approach would be ideal to solve this problem.

` 1---2---3---4---5---6--NULL  [Level 0]         |         7---8---9---10--NULL [Level 1]             |             11--12--NULL     [Level 2]`

If we traverse the doubly linked list starting from its head and go down whenever a node has a child, the issue is less about going from the head node down to eventually the last node in the last level (12) but more about how do we keep that reference of the nodes that we’ve haven’t traversed in the previous levels (i.e. 9, 10 in Level 1 and 4, 5, 6 in Level 0).

The way in which we can solve this problem is by using a Stack data structure. As we come across a node that has a child node but also its next pointer is pointing to another node at the same level, then we want to add that next node in the linear chain at the same level into our Stack and proceed to traverse the child node. This will repeat level-by-level until we get to node 12 in which we know that we’ve reached a dead-end. At that point, we can check if our Stack is not empty and if it isn’t, then we know that there are nodes that we still need to add to our result (flattened doubly linked list).

As we’re working with a doubly linked list, we’ll need to make sure that we are establishing not only the next pointer but also the previous pointer throughout our algorithm (i.e. when we are traversing to a child node and when we are adding nodes stored into our Stack back into our flattened doubly linked list).