## Similar Problems

Similar Problems not available

# Flatten A Multilevel Doubly Linked List - Leetcode Solution

LeetCode: Flatten A Multilevel Doubly Linked List Leetcode Solution

Difficulty: Medium

Topics: linked-list depth-first-search

The Flatten A Multilevel Doubly Linked List problem on LeetCode is a popular coding problem that requires us to flatten a given multi-level doubly linked list into a single-level doubly linked list. In this problem, each node of the input list can either have no child node or one child node, which in turn can have one or no child nodes, and so on. The goal is to rearrange the list such that all the child nodes are appended to the end of their parent node, and all the previous and next pointers are updated accordingly. In this article, we will discuss the problem statement in detail, understand the approach to solve the problem, and provide the Python code for the solution.

Problem Statement:

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. 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 below example.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example:

Input: 1 <--> 2 <--> 3 <--> 4 <--> 5 <--> 6 <--> NULL | 7 <--> 8 <--> 9 <--> 10 <--> NULL | 11 <--> 12 <--> NULL

Output: 1 <--> 2 <--> 3 <--> 7 <--> 8 <--> 11 <--> 12 <--> 9 <--> 10 <--> 4 <--> 5 <--> 6 <--> NULL

Approach:

To solve the Flatten a Multilevel Doubly Linked List problem, we can use recursion and traverse the given list in depth-first fashion. For each node, if it has a child node, we will recursively flatten the child list and append it to the end of the parent list. We will keep track of the tail of the parent list, which is the last node in the current flattened list. After flattening the child list, we will set the current node's child pointer to None and update the next and previous pointers of the child nodes accordingly.

The recursive function would look like this:

```
def flattenList(node):
if not node:
return node
dummy = Node(0, None, node, None)
tail = dummy
stack = [node]
while stack:
curr = stack.pop()
tail.next = curr
curr.prev = tail
if curr.next:
stack.append(curr.next)
if curr.child:
stack.append(curr.child)
curr.child = None
tail = curr
dummy.next.prev = None
return dummy.next
```

In the above code, we first create a dummy node and initialize the tail of the flattened list to be the dummy node. We then use a stack to keep track of the nodes that need to be processed. We start by pushing the first node onto the stack. Then, for each node, we set its prev pointer to the tail of the flattened list, and set the next pointer of the tail to the current node. We then update the tail to be the current node.

If the current node has a child, we push the child onto the stack and set the child pointer of the current node to be None. This ensures that we visit the child nodes next and append them to the flattened list. Finally, we reset the prev pointer of the first node to None and return the flattened list.

Code:

Here is the complete Python code for the Flatten a Multilevel Doubly Linked List problem:

```
class Node:
def __init__(self, val=None, prev=None, next=None, child=None):
self.val = val
self.prev = prev
self.next = next
self.child = child
def flattenList(node):
if not node:
return node
dummy = Node(0, None, node, None)
tail = dummy
stack = [node]
while stack:
curr = stack.pop()
tail.next = curr
curr.prev = tail
if curr.next:
stack.append(curr.next)
if curr.child:
stack.append(curr.child)
curr.child = None
tail = curr
dummy.next.prev = None
return dummy.next
```

This solution has a time complexity of O(N), where N is the total number of nodes in the input list. The space complexity is O(N), as we need to use a stack to keep track of the nodes that need to processed.

## Flatten A Multilevel Doubly Linked List Solution Code

`1`