Leetcode #: 430
Name: Flatten a Multilevel Doubly Linked List
Difficulty: Medium
Url: https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/
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).
Code
Thank you for reading!
In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.
If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com
