430. Flatten a Multilevel Doubly Linked List
Asked at Adobe
Difficulty
Medium
Time
O(n)
Space
O(d)
Pattern
Linked List
Companies
1
Problem
You are given the head of a doubly linked list. Each node has three pointers: next, prev, and an extra child pointer. A child points to another doubly linked list of the same kind, and those child lists can have children too, so the whole thing looks like several levels stacked on top of each other.
Your job is to flatten this structure into one single-level doubly linked list. The rule is: if a node curr has a child list, then all nodes of that child list must appear right after curr and before curr.next in the final list. This rule applies at every level, so a child of a child also gets inserted in the same way.
Return the head of the flattened list. Every node in the result must have its child pointer set to null, and the prev/next pointers must form a correct doubly linked list from head to tail. If the input is empty, return null.
Note: the input is given in a special serialized form. Each level is written as a list, and null entries mark positions where that level has no node under the upper level's node. The levels are merged into one array, and trailing nulls are removed.
A list with child levels
Constraints
- ●
The number of nodes is at most 1000. - ●
1 <= Node.val <= 10^5 - ●
Each node has next, prev and child pointers. - ●
The input may be an empty list.
Examples
head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12][1,2,3,7,8,11,12,9,10,4,5,6]head = [1,2,null,3][1,3,2]head = [][]Asked At
1 companies| 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.
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).
DFS: flatten child, then splice it in
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
O(n) time"""
# 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 runs in O(n) time and O(d) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.