Flatten a Multilevel Doubly Linked List
Asked at Adobe
Problem
Given a multilevel doubly linked list where nodes may have a child pointer, flatten the list so that all nodes appear in a single-level doubly linked list. The child list should be inserted between the current node and its next node. This tests your ability to manage multiple pointers during traversal.
Asked At
| Company | Difficulty | |
|---|---|---|
| Adobe | Medium | View all Adobe questions → |
How to Think About It
The key insight: when you encounter a node with a child, you need to:
- Save the node's next pointer
- Insert the child list between the current node and its next
- Connect the end of the child list to the saved next node
- Continue traversing from the child (not the next)
DFS approach: traverse the list. When you find a node with a child, recursively flatten the child list. Insert it after the current node. Connect the tail of the flattened child to the original next node.
Why DFS works: the child list might itself have children. DFS flattens from the deepest level up, so by the time you process a node, all its children are already flattened.
Visual walkthrough:
1 -> 2 -> 3 -> 4 -> 5 -> 6
|
7 -> 8 -> 9 -> 10
|
11 -> 12
Step 1: At node 3, child = 7. DFS processes 7 -> 8 (has child 11 -> 12). Flattened 8: 8 -> 11 -> 12 -> 9 -> 10. Then 7 -> 8 -> 11 -> 12 -> 9 -> 10.
Insert after 3: 3 -> 7 -> 8 -> 11 -> 12 -> 9 -> 10 -> 4 -> 5 -> 6.
Result: 1 -> 2 -> 3 -> 7 -> 8 -> 11 -> 12 -> 9 -> 10 -> 4 -> 5 -> 6.
Edge cases: no child pointers (list is already flat), child at the last node (child's tail connects to null), multiple levels deep (DFS handles recursively).
Optimal Approach
Iterative approach with a stack:
Step 1: Start at head. Use a stack to track nodes to process.
Step 2: For each node:
- If it has a child: save next, push next onto stack, connect child after current, advance to child
- If no child and has next: advance to next
- If no next: pop from stack (go back to parent's next), connect tail to it
DFS approach:
Step 1: Traverse the list.
Step 2: When a node has a child:
- Flatten the child recursively
- Insert the flattened child between current and current.next
- Connect the child's tail to current.next
- Set current.child = None
Time: O(n) -- each node visited once. Space: O(d) where d = maximum depth (DFS stack).
What Trips People Up in Real Interviews
Losing the next pointer before inserting the child. Always save curr.next before modifying pointers. If you overwrite next without saving it, you lose the rest of the list.
Not connecting the tail of the child list to the original next node. After inserting the flattened child, its last node must point to the original next. Without this connection, the list is truncated.
Forgetting to set child = None after flattening. The problem says child pointers should be null in the flattened list. Clear them as you process.
Confusing the traversal order. You must process the child FIRST, then continue with the next node. If you process next first, you'll insert the child in the wrong place.
Not handling the doubly-linked list correctly. When you insert the child list, you must set both child_head.prev and child_tail.next. Forgetting the prev pointer breaks the doubly-linked property.
Solution Code
"""
# 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):
if not head:
return head
curr = head
while curr:
if curr.child:
next_node = curr.next
child_head = self.flatten(curr.child)
child_tail = child_head
while child_tail.next:
child_tail = child_tail.next
curr.next = child_head
child_head.prev = curr
child_tail.next = next_node
if next_node:
next_node.prev = child_tail
curr.child = None
curr = curr.next
return headFrequently Asked Questions
What is the Flatten a Multilevel Doubly Linked List problem?
Given a multilevel doubly linked list where nodes may have a child pointer, flatten the list so that all nodes appear in a single-level doubly linked list. The child list should be inserted between the current node and its next node. This tests your ability to manage multiple pointers during traversal.
How do you solve Flatten a Multilevel Doubly Linked List?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Flatten a Multilevel Doubly Linked List?
Flatten a Multilevel Doubly Linked List is asked at Adobe. It is a medium difficulty problem.
What are common mistakes on Flatten a Multilevel Doubly Linked List?
- Losing the next pointer before inserting the child. Always save `curr.next` before modifying pointers. If you overwrite next without saving it, you lose the rest of the list.
- Not connecting the tail of the child list to the original next node. After inserting the flattened child, its last node must point to the original next. Without this connection, the list is truncated.
- Forgetting to set `child = None` after flattening. The problem says child pointers should be null in the flattened list. Clear them as you process.
- Confusing the traversal order. You must process the child FIRST, then continue with the next node. If you process next first, you'll insert the child in the wrong place.
- Not handling the doubly-linked list correctly. When you insert the child list, you must set both `child_head.prev` and `child_tail.next`. Forgetting the prev pointer breaks the doubly-linked property.