We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Flatten a Multilevel Doubly Linked List

Number: 766

Difficulty: Medium

Paid? No

Companies: Bloomberg, Google, Amazon, Meta, Apple

Problem Description

Given a doubly linked list where each node has an extra child pointer that may point to a separate doubly linked list, flatten the list so that all nodes appear in a single-level doubly linked list. The ordering should follow a depth-first traversal, where if a node has a child, the entire child list is inserted between that node and its next node. All child pointers should be set to null in the final flattened list.

Key Insights

  • Use a depth-first traversal to process child lists before proceeding to the next pointer.
  • When a node with a child is found, recursively flatten the child list.
  • Splice the flattened child list in between the current node and the next node.
  • Maintain previous and next pointers correctly to preserve the doubly linked list properties.
  • Ensure that all child pointers are set to null after flattening.

Space and Time Complexity

Time Complexity: O(n), where n is the total number of nodes, since each node is processed exactly once. Space Complexity: O(n) in the worst-case due to recursion stack in case of a highly nested list.

Solution

We can solve this problem using a recursive depth-first search (DFS) approach. The main idea is to traverse the list and, whenever a node with a child pointer is encountered, recursively flatten its child list. Once the child list is flattened, it can be spliced into the main list between the current node and the node originally following it. We then continue processing the next pointer. This ensures that the entire list is flattened in depth-first order. The recursive helper function returns the tail of the flattened segment, which is used to connect the subsequent parts of the list correctly.

Code Solutions

# Definition for a Node.
class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

def flatten(head):
    # If the list is empty, simply return None.
    if not head:
        return head

    # Helper function to perform DFS and return the tail of the flattened list.
    def dfs(node):
        current = node
        last = None
        while current:
            next_node = current.next  # Store current.next before modifications
            # If current node has a child, we flatten the child list recursively.
            if current.child:
                # Recursively flatten the child list.
                child_tail = dfs(current.child)
                # Connect current node with the start of the child list.
                current.next = current.child
                current.child.prev = current
                # If there was a next node, attach it after the child list.
                if next_node:
                    child_tail.next = next_node
                    next_node.prev = child_tail
                # Set child pointer to None as required.
                current.child = None
                # Update the tail pointer.
                last = child_tail
            else:
                last = current
            # Move to the next node (which might have been updated after flattening a child).
            current = next_node
        return last

    dfs(head)  # Begin DFS traversal from the head.
    return head

# Example to illustrate usage:
# head = Node(1)
# head.next = Node(2)
# head.child = Node(3)
# flatten(head)
← Back to All Questions