Problem Description

You have a special doubly linked list where each node contains:

• A next pointer (pointing to the next node)
• A prev pointer (pointing to the previous node)
• A child pointer (which may point to another doubly linked list)

This creates a multilevel data structure where nodes can have "child" lists branching off them, and those child lists can have their own children, creating multiple levels.

Your task is to flatten this multilevel structure into a single-level doubly linked list.

The flattening rules are:

1. When you encounter a node with a child list, the child list should be inserted right after the current node
2. The child list nodes should appear after the current node but before the current node's original next node
3. After flattening, all nodes should be in a single level with proper prev and next connections
4. All child pointers must be set to null after flattening

For example, if node A has next node B and child node C (which has its own list C->D->E), after flattening the order would be: A->C->D->E->B.

The function should return the head of the flattened list. If the input head is null, return null.

The solution uses a recursive approach that performs a preorder-like traversal. It processes each node by:

1. Connecting it to the previous node with proper prev and next pointers
2. Saving the original next node
3. Recursively flattening the child list first
4. Then continuing with the original next node
5. Setting the child pointer to null after processing

A dummy node is used to simplify edge cases when connecting the head of the list.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While this problem involves a linked list structure, the multilevel nature with child pointers creates a graph-like structure. Each node can be viewed as a vertex, and the next, prev, and child pointers represent edges between nodes. The child pointers specifically create a tree-like branching structure.

Is it a tree?

• Yes: The multilevel doubly linked list with child pointers forms a tree structure. Each node can have at most one child branch, and there are no cycles (a node's child list doesn't loop back to any ancestor). The main list with child branches hanging off it creates a tree where:
  • The main horizontal list forms the primary path
  • Child pointers create subtrees branching downward
  • Each subtree can have its own branches

DFS

• Yes: Since we identified this as a tree structure, the flowchart leads us to use DFS (Depth-First Search).

Conclusion: The flowchart suggests using DFS for this problem.

This makes perfect sense because:

1. We need to traverse into child lists (going deep) before continuing with the next sibling
2. When we encounter a node with a child, we must fully explore and flatten that child's subtree before moving to the original next node
3. The recursive nature of DFS naturally handles the multilevel structure - we dive deep into child lists, flatten them completely, then backtrack to continue with the main list
4. The solution's preorder function is essentially a DFS traversal that processes nodes in a depth-first manner, exploring child branches before siblings

Intuition

When we look at this multilevel linked list, we can think of it like a document with nested bullet points. The main list is like the top-level bullets, and child lists are like sub-bullets that need to be "promoted" to the same level.

The key insight is that when we encounter a node with a child, we need to:

1. Remember where we were going (save the next node)
2. Explore the entire child branch first
3. Insert all those child nodes into our main path
4. Then continue where we left off

This naturally suggests a recursive DFS approach. Why? Because each time we see a child, we face the exact same subproblem - we need to flatten that child's list and connect it properly. The child might have its own children, creating a recursive structure.

Think of it like exploring a maze where some rooms have trapdoors to lower levels. When you find a trapdoor (child pointer), you:

• Mark your current position
• Go down and explore the entire lower level
• Come back up with all the rooms from below "flattened" into your current path
• Continue exploring from where you left off

The clever part of the solution is how it maintains connections while traversing. As we visit each node in DFS order, we immediately establish the prev and next connections with the previous node. This way, we're building the flattened list as we traverse, rather than collecting nodes first and then connecting them.

The preorder function returns the tail of the processed segment, which is crucial. After processing a child branch, we need to know where that branch ends so we can connect it to the original next node. This tail-tracking ensures we maintain proper connections throughout the recursive calls.

Using a dummy node at the start simplifies edge cases - we don't need special logic for connecting the very first node, as it's treated like any other node in the traversal.

Solution Approach

The solution implements a recursive DFS traversal with careful pointer manipulation. Let's break down the implementation step by step:

Core Function - preorder(pre, cur):

This recursive function takes two parameters:

• pre: the previous node that should connect to cur
• cur: the current node being processed

The function returns the tail (last node) of the flattened segment starting from cur.

Key Steps in Each Recursive Call:

1. Base Case: If cur is None, return pre as there's nothing to process.

2. Connect Current Node:

   cur.prev = pre
   pre.next = cur

   This establishes the doubly-linked connection between the previous and current nodes.

3. Save Original Next:

   t = cur.next

   Before diving into the child, we save the original next pointer because we'll need to reconnect to it later.

4. Process Child Branch:

   tail = preorder(cur, cur.child)
   cur.child = None

   Recursively flatten the child branch if it exists. The function returns the tail of the flattened child segment. We also set child to None as required.

5. Continue with Original Next:

   return preorder(tail, t)

   Connect the tail of the child segment (or current node if no child) to the original next node and continue processing.

Main Function Logic:

1. Handle empty list case by returning None

2. Create a dummy node:

   dummy = Node(0, None, head, None)

   This simplifies the logic by treating the head like any other node.

3. Start the recursive flattening:

   preorder(dummy, head)

4. Clean up and return:

   dummy.next.prev = None
   return dummy.next

   Remove the connection from head back to dummy and return the actual head.

Why This Works:

The algorithm processes nodes in the exact order they should appear in the final flattened list:

• Current node first
• Then all nodes in the child subtree (recursively flattened)
• Finally, the original next node and its subsequent nodes

The tail-tracking mechanism ensures that after processing each segment, we know exactly where to attach the next segment, maintaining proper doubly-linked connections throughout.

Time Complexity: O(n) where n is the total number of nodes, as each node is visited exactly once.

Space Complexity: O(d) where d is the maximum depth of the multilevel structure, due to the recursive call stack.

Example Walkthrough

Let's walk through a small example to illustrate how the solution flattens a multilevel doubly linked list.

Initial Structure:

1---2---3---4
    |
    5---6
        |
        7---8

We want to flatten this into: 1->2->5->6->7->8->3->4

Step-by-step execution:

1. Start with dummy node

   • Create dummy node pointing to head (1)
   • Call preorder(dummy, node_1)

2. Process node 1

   • Connect: dummy.next = 1, 1.prev = dummy
   • Node 1 has no child
   • Save t = node_2
   • Call preorder(node_1, node_2)

3. Process node 2

   • Connect: 1.next = 2, 2.prev = 1
   • Node 2 has child (node 5)!
   • Save t = node_3 (original next)
   • Call preorder(node_2, node_5) to process child branch

4. Process node 5 (child branch)

   • Connect: 2.next = 5, 5.prev = 2
   • Node 5 has no child
   • Save t = node_6
   • Call preorder(node_5, node_6)

5. Process node 6

   • Connect: 5.next = 6, 6.prev = 5
   • Node 6 has child (node 7)!
   • Save t = None (no next)
   • Call preorder(node_6, node_7)

6. Process node 7 (nested child)

   • Connect: 6.next = 7, 7.prev = 6
   • Node 7 has no child
   • Save t = node_8
   • Call preorder(node_7, node_8)

7. Process node 8

   • Connect: 7.next = 8, 8.prev = 7
   • Node 8 has no child and no next
   • Returns node 8 as tail

8. Backtrack and continue

   • Back to step 6: tail of node 7's branch is node 8
   • Back to step 5: tail of node 6's branch is node 8
   • Back to step 4: tail of node 5's branch is node 8
   • Back to step 3: tail of child branch is node 8
   • Now connect tail (node 8) to saved next (node 3)
   • Call preorder(node_8, node_3)

9. Process node 3 (original path)

   • Connect: 8.next = 3, 3.prev = 8
   • Node 3 has no child
   • Save t = node_4
   • Call preorder(node_3, node_4)

10. Process node 4

    • Connect: 3.next = 4, 4.prev = 3
    • Node 4 has no child and no next
    • Returns node 4 as final tail

Final Result:

dummy -> 1 <-> 2 <-> 5 <-> 6 <-> 7 <-> 8 <-> 3 <-> 4

After cleanup (removing dummy), we get:

1 <-> 2 <-> 5 <-> 6 <-> 7 <-> 8 <-> 3 <-> 4

All child pointers are set to None, and the list is properly flattened with all nodes connected via prev and next pointers only.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the total number of nodes in the multilevel doubly linked list.

The algorithm visits each node exactly once through the recursive preorder function. For each node, it performs constant time operations:

• Setting cur.prev = pre - O(1)
• Setting pre.next = cur - O(1)
• Storing cur.next in temporary variable - O(1)
• Setting cur.child = None - O(1)
• Making recursive calls that collectively cover all nodes

Since each node is processed exactly once with constant time operations, the total time complexity is O(n).

Space Complexity: O(d) where d is the maximum depth of the multilevel structure.

The space complexity comes from the recursive call stack. In the worst case, when we have a deeply nested structure (like a linked list where each node has a child forming a chain), the recursion depth can be at most d. Each recursive call uses O(1) space for local variables (t variable and parameters), so the total space used by the call stack is O(d).

In the worst case where the list forms a single chain through child pointers, d = n, making the space complexity O(n). In the best case where the list is completely flat with no child pointers, d = 1, making the space complexity O(1).

Common Pitfalls

1. Forgetting to Save the Original Next Pointer

One of the most common mistakes is not saving the original next pointer before processing the child branch. If you directly process the child without saving next, you'll lose the reference to the rest of the original list.

Incorrect approach:

def flatten_dfs(prev_node, curr_node):
    if curr_node is None:
        return prev_node
  
    curr_node.prev = prev_node
    prev_node.next = curr_node
  
    # ❌ Wrong: Processing child without saving next
    tail = flatten_dfs(curr_node, curr_node.child)
    curr_node.child = None
  
    # curr_node.next is already lost/overwritten!
    return flatten_dfs(tail, curr_node.next)

Why this fails: When we recursively process the child, the child nodes will overwrite curr_node.next. By the time we try to access curr_node.next, it no longer points to the original next node but to the first child node.

Solution: Always save the next pointer before processing children:

temp_next = curr_node.next  # Save it first!
tail = flatten_dfs(curr_node, curr_node.child)
curr_node.child = None
return flatten_dfs(tail, temp_next)  # Use the saved reference

2. Not Properly Handling the Dummy Node's Connections

Another common pitfall is forgetting to clean up the dummy node's connection to the actual head, which can create an invalid doubly-linked list where the head has a non-null prev pointer.

Incorrect approach:

def flatten(self, head):
    if head is None:
        return None
  
    dummy = Node(0, None, head, None)
    flatten_dfs(dummy, head)
  
    # ❌ Wrong: Forgetting to disconnect dummy from head
    return head  # head.prev still points to dummy!

Why this fails: The head of a doubly-linked list should have prev = None. If we don't disconnect the dummy node, the head will have prev pointing to the dummy node, violating the expected structure.

Solution: Always disconnect the dummy node:

dummy.next.prev = None  # Disconnect dummy from the result
return dummy.next       # Return the actual head

3. Forgetting to Set Child Pointers to None

The problem explicitly requires all child pointers to be null after flattening. Forgetting this step leaves dangling child pointers that create an invalid structure.

Incorrect approach:

def flatten_dfs(prev_node, curr_node):
    if curr_node is None:
        return prev_node
  
    curr_node.prev = prev_node
    prev_node.next = curr_node
  
    temp_next = curr_node.next
    tail = flatten_dfs(curr_node, curr_node.child)
  
    # ❌ Wrong: Forgetting to clear child pointer
    # curr_node.child = None  # Missing this line!
  
    return flatten_dfs(tail, temp_next)

Why this fails: The flattened list should be a pure doubly-linked list with no child pointers. Leaving child pointers intact means the structure isn't truly flattened.

Solution: Always set child to None after processing:

tail = flatten_dfs(curr_node, curr_node.child)
curr_node.child = None  # Clear the child pointer