Solution For Flatten A Multilevel Doubly Linked List
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.
Step by Step Implementation For Flatten A Multilevel Doubly Linked List
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
};
*/
class Solution {
public Node flatten(Node head) {
// Base case
if (head == null) {
return head;
}
// Recursive case
// Step 1: Flatten child list
Node child = flatten(head.child);
head.child = null;
// Step 2: Append child list to current list
if (child != null) {
Node tail = child;
while (tail.next != null) {
tail = tail.next;
}
tail.next = head.next;
if (head.next != null) {
head.next.prev = tail;
}
head.next = child;
child.prev = head;
}
// Step 3: Flatten remaining list
return flatten(head.next);
}
}# Definition for a Node.
class Node:
def __init__(self, val, prev, next, child):
self.val = val
self.prev = prev
self.next = next
self.child = child
class Solution:
def flatten(self, head: 'Node') -> 'Node':
if not head:
return head
# Pointers to keep track of the current and previous node
curr, prev = head, None
# Stack to keep track of all the child nodes
stack = []
# Loop until there are no more nodes
while curr:
# If the current node has a child
if curr.child:
# If the current node has a next, push it to the stack
if curr.next:
stack.append(curr.next)
# Make the child node the new next
curr.next = curr.child
# Make the child's previous the current node
curr.child.prev = curr
# Set child to None
curr.child = None
# If the current node does not have a child, check if it has a next
elif not curr.next and stack:
# If it does not have a next, set the next as the top node from the stack
curr.next = stack.pop()
# Set the next node's previous as the current node
curr.next.prev = curr
# Set the previous node as the current node
prev = curr
# Move to the next node
curr = curr.next
# Return the head of the flattened list
return head//Solution:
/*
Given a multilevel doubly linked list, flatten it to a single level doubly linked list. You are given the head of the first level of the list.
*/
// flatten a multilevel doubly linked list
// we can use a stack to keep track of the nodes at each level
// we can also use a prev variable to keep track of the previous node
function flattenList(head) {
if (!head) return null;
let stack = [head];
let prev = null;
while (stack.length) {
let curr = stack.pop();
// if we have a previous node, make its next point to the current node
if (prev) {
prev.next = curr;
}
// if the current node has a child, add it to the stack
if (curr.child) {
stack.push(curr.child);
}
// if the current node has a next, add it to the stack
if (curr.next) {
stack.push(curr.next);
}
// mark the current node as visited
curr.child = null;
prev = curr;
}
return head;
}/**
* // Definition for a Node.
* class Node {
* public:
* int val;
* Node* prev;
* Node* next;
* Node* child;
* };
*/
class Solution {
public:
Node* flatten(Node* head) {
if (!head) return head;
stack stk;
stk.push(head);
while (!stk.empty()) {
Node* curr = stk.top();
stk.pop();
if (curr->next) {
stk.push(curr->next);
}
if (curr->child) {
stk.push(curr->child);
curr->child = nullptr;
}
if (!stk.empty()) {
curr->next = stk.top();
}
if (curr->next) {
curr->next->prev = curr;
}
}
return head;
}
}; /*
// Definition for a Node.
public class Node {
public int val;
public Node prev;
public Node next;
public Node child;
public Node(){}
public Node(int _val,Node _prev,Node _next,Node _child) {
val = _val;
prev = _prev;
next = _next;
child = _child;
}
*/
public class Solution {
public Node Flatten(Node head) {
// Base case
if (head == null)
return head;
// Initialize current as head
Node current = head;
/*
To understand this algorithm, let us consider the
below example
5 -> 10 -> 19 -> 28
| | | |
7 20 22 35
| | |
8 50 40
| |
30 45
We have discussed a similar algorithm to flatten
a linked list with next pointers. The only difference
here is that now next pointer points to a child node
and not the next node in the list. So we need to traverse
down the current node's child list and keep going until
we reach the end of the list.
5 -> 7 -> 8 -> 10 -> 19 -> 20 -> 22 -> 28 -> 30 -> 35 -> 40 -> 45
| |
7 8
| |
8 50
We have discussed a similar algorithm to flatten
a linked list with next pointers. The only difference
here is that now next pointer points to a child node
and not the next node in the list. So we need to traverse
down the current node's child list and keep going until
we reach the end of the list.
*/
// Iterate till the end of the linked list
while (current != null)
{
// If current node has a child
if (current.child != null)
{
// Then we need to save its next node before
// we change its next pointer
Node temp = current.next;
// Now we should point the current node's next
// to its child
current.next = current.child;
current.next.prev = current;
current.child = null;
// We need to iterate to the end of the current node's
// child and point the last node's next to the saved
// next of the current node
while (current.next != null)
current = current.next;
current.next = temp;
// If 'temp' is not null, then it represents the next
// node of the original list. So we need to set the 'prev'
// pointer of the next node to the current node
if (temp != null)
temp.prev = current;
}
// Go to the next node
current = current.next;
}
return head;
}
}