Flatten A Multilevel Doubly Linked List

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


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]