Flatten A Multilevel Doubly Linked List - Leetcode Solution

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.

1