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; stackstk; 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; } }