430. Flatten a Multilevel Doubly Linked List - Detailed Explanation

Problem Statement

Description:
You are given the head of a doubly linked list where in addition to the next and prev pointers, each node has a child pointer that may or may not point to a separate doubly linked list. Flatten the list such that all the nodes appear in a single-level, doubly linked list. The nodes should appear in the same order as a depth-first traversal.

Example 1:

• Input:
  A list represented visually as:

  1 --- 2 --- 3 --- 4 --- 5 --- 6
             |
             7 --- 8 --- 9 --- 10
                   |
                   11--12
  

• Output:
  The flattened list should be:

  1 --- 2 --- 3 --- 7 --- 8 --- 11 --- 12 --- 9 --- 10 --- 4 --- 5 --- 6
  

• Explanation:
  The child list starting at node 7 is inserted between 3 and 4. Node 8’s child list (11–12) is inserted between 8 and 9.

Example 2:

• Input:
  A list with a single node with no child.
• Output:
  The same single node.
• Explanation:
  There is nothing to flatten.

Example 3:

• Input:
  A list where every node has a child and the structure is deeply nested.
• Output:
  A fully flattened list following the depth-first traversal order.

Constraints:

• The number of nodes in the list is in the range [0, N].
• The value of each node is an integer.
• The child pointer of a node might be null.
• The list might be empty (i.e., head is null).

Hints Before Solving

• Hint 1: Consider performing a depth-first traversal. When you encounter a node with a child, recursively flatten that child list and insert it between the current node and the next node.
• Hint 2: Think about how to reconnect the prev and next pointers after inserting the flattened child list.
• Hint 3: You might need to return the tail of the flattened sublist to link it properly with the remaining part of the main list.

Approaches to Solve the Problem

Approach 1: Recursive Depth-First Search (DFS)

Explanation:

• Idea:
  Use recursion to process the list. For each node, if a child exists, recursively flatten the child list and splice it between the current node and its next node.
• Steps:
  1. Start at the head and iterate through each node.
  2. When you find a node with a child:
     • Recursively flatten the child list.
     • Connect the current node’s next pointer to the head of the flattened child list.
     • Connect the flattened child list’s tail to the original next node.
     • Set the child pointer of the current node to null.
  3. Return the tail of the flattened list to help in linking lists at higher levels.

Visual Walkthrough:

Imagine you are at node 3 in the list. Node 3 has a child pointing to node 7. You flatten the list starting from 7, which gives you a sublist (7 → 8 → 11 → 12 → 9 → 10). Then, you insert this flattened sublist between 3 and 4, adjusting the pointers accordingly.

Approach 2: Iterative Using a Stack

Explanation:

• Idea:
  Use a stack to mimic recursion and perform a depth-first traversal iteratively.
• Steps:
  1. Initialize a pointer to the head and an empty stack.
  2. Traverse the list:
     • If the current node has a child and a next node, push the next node onto the stack.
     • Set the current node’s next pointer to its child and update the prev pointer.
     • Set the child pointer to null.
  3. When you reach a node with no next pointer, pop a node from the stack (if available) and attach it as the next node.
  4. Continue until the stack is empty and the list is fully flattened.

Code Implementations

Python Implementation