Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure.
Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.
Input/Output Specifications
- Input: Head of a multilevel doubly linked list
- Output: Head of the flattened doubly linked list
- Constraints:
- The number of nodes will not exceed 1000
- 1 <= Node.val <= 10^5
Examples
Example 1:
Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Example 2:
Input: head = [1,2,null,3]
Output: [1,3,2]
Example 3:
Input: head = []
Output: []
Solutions
Approach 1: Iterative (Stack)
This approach uses a stack to process child nodes when encountered.
Algorithm:
- Traverse the list from head to tail
- When a node with a child is found:
- Store the next node in a stack
- Connect current node to its child
- Set child’s prev to current node
- Set child to null
- When reaching the end, pop from stack and continue
- Return the flattened list
Python:
def flatten(head):
"""
Flatten multilevel doubly linked list using stack
Time: O(n)
Space: O(n)
"""
if not head:
return head
stack = []
current = head
while current:
if current.child:
# Store next node if it exists
if current.next:
stack.append(current.next)
# Connect current to child
current.next = current.child
current.child.prev = current
current.child = None
# Move to next node
if current.next:
current = current.next
elif stack:
# Connect to next node from stack
current.next = stack.pop()
current.next.prev = current
current = current.next
else:
break
return head
Java:
class Solution {
/**
* Flatten multilevel doubly linked list using stack
* Time: O(n)
* Space: O(n)
*/
public Node flatten(Node head) {
if (head == null) {
return head;
}
Stack<Node> stack = new Stack<>();
Node current = head;
while (current != null) {
if (current.child != null) {
// Store next node if it exists
if (current.next != null) {
stack.push(current.next);
}
// Connect current to child
current.next = current.child;
current.child.prev = current;
current.child = null;
}
// Move to next node
if (current.next != null) {
current = current.next;
} else if (!stack.isEmpty()) {
// Connect to next node from stack
current.next = stack.pop();
current.next.prev = current;
current = current.next;
} else {
break;
}
}
return head;
}
}
Go:
// flatten - Flatten multilevel doubly linked list using stack
// Time: O(n)
// Space: O(n)
func flatten(head *Node) *Node {
if head == nil {
return head
}
stack := make([]*Node, 0)
current := head
for current != nil {
if current.Child != nil {
// Store next node if it exists
if current.Next != nil {
stack = append(stack, current.Next)
}
// Connect current to child
current.Next = current.Child
current.Child.Prev = current
current.Child = nil
}
// Move to next node
if current.Next != nil {
current = current.Next
} else if len(stack) > 0 {
// Connect to next node from stack
current.Next = stack[len(stack)-1]
stack = stack[:len(stack)-1]
current.Next.Prev = current
current = current.Next
} else {
break
}
}
return head
}
JavaScript:
/**
* Flatten multilevel doubly linked list using stack
* Time: O(n)
* Space: O(n)
*/
function flatten(head) {
if (head === null) {
return head;
}
const stack = [];
let current = head;
while (current !== null) {
if (current.child !== null) {
// Store next node if it exists
if (current.next !== null) {
stack.push(current.next);
}
// Connect current to child
current.next = current.child;
current.child.prev = current;
current.child = null;
}
// Move to next node
if (current.next !== null) {
current = current.next;
} else if (stack.length > 0) {
// Connect to next node from stack
current.next = stack.pop();
current.next.prev = current;
current = current.next;
} else {
break;
}
}
return head;
}
C#:
public class Solution {
/// <summary>
/// Flatten multilevel doubly linked list using stack
/// Time: O(n)
/// Space: O(n)
/// </summary>
public Node Flatten(Node head) {
if (head == null) {
return head;
}
Stack<Node> stack = new Stack<Node>();
Node current = head;
while (current != null) {
if (current.child != null) {
// Store next node if it exists
if (current.next != null) {
stack.Push(current.next);
}
// Connect current to child
current.next = current.child;
current.child.prev = current;
current.child = null;
}
// Move to next node
if (current.next != null) {
current = current.next;
} else if (stack.Count > 0) {
// Connect to next node from stack
current.next = stack.Pop();
current.next.prev = current;
current = current.next;
} else {
break;
}
}
return head;
}
}
Approach 2: Recursive
This approach uses recursion to flatten child lists when encountered.
Algorithm:
- Traverse the list from head to tail
- When a node with a child is found:
- Recursively flatten the child list
- Connect current node to flattened child
- Set child’s prev to current node
- Set child to null
- Return the flattened list
Python:
def flattenRecursive(head):
"""
Flatten multilevel doubly linked list using recursion
Time: O(n)
Space: O(n) - recursion stack
"""
if not head:
return head
current = head
while current:
if current.child:
# Recursively flatten child list
flattened_child = flattenRecursive(current.child)
# Store next node
next_node = current.next
# Connect current to flattened child
current.next = flattened_child
flattened_child.prev = current
current.child = None
# Find end of flattened child
while flattened_child.next:
flattened_child = flattened_child.next
# Connect end of child to next node
flattened_child.next = next_node
if next_node:
next_node.prev = flattened_child
current = current.next
return head
Java:
class Solution {
/**
* Flatten multilevel doubly linked list using recursion
* Time: O(n)
* Space: O(n) - recursion stack
*/
public Node flattenRecursive(Node head) {
if (head == null) {
return head;
}
Node current = head;
while (current != null) {
if (current.child != null) {
// Recursively flatten child list
Node flattenedChild = flattenRecursive(current.child);
// Store next node
Node nextNode = current.next;
// Connect current to flattened child
current.next = flattenedChild;
flattenedChild.prev = current;
current.child = null;
// Find end of flattened child
while (flattenedChild.next != null) {
flattenedChild = flattenedChild.next;
}
// Connect end of child to next node
flattenedChild.next = nextNode;
if (nextNode != null) {
nextNode.prev = flattenedChild;
}
}
current = current.next;
}
return head;
}
}
Go:
// flattenRecursive - Flatten multilevel doubly linked list using recursion
// Time: O(n)
// Space: O(n) - recursion stack
func flattenRecursive(head *Node) *Node {
if head == nil {
return head
}
current := head
for current != nil {
if current.Child != nil {
// Recursively flatten child list
flattenedChild := flattenRecursive(current.Child)
// Store next node
nextNode := current.Next
// Connect current to flattened child
current.Next = flattenedChild
flattenedChild.Prev = current
current.Child = nil
// Find end of flattened child
for flattenedChild.Next != nil {
flattenedChild = flattenedChild.Next
}
// Connect end of child to next node
flattenedChild.Next = nextNode
if nextNode != nil {
nextNode.Prev = flattenedChild
}
}
current = current.Next
}
return head
}
JavaScript:
/**
* Flatten multilevel doubly linked list using recursion
* Time: O(n)
* Space: O(n) - recursion stack
*/
function flattenRecursive(head) {
if (head === null) {
return head;
}
let current = head;
while (current !== null) {
if (current.child !== null) {
// Recursively flatten child list
const flattenedChild = flattenRecursive(current.child);
// Store next node
const nextNode = current.next;
// Connect current to flattened child
current.next = flattenedChild;
flattenedChild.prev = current;
current.child = null;
// Find end of flattened child
let end = flattenedChild;
while (end.next !== null) {
end = end.next;
}
// Connect end of child to next node
end.next = nextNode;
if (nextNode !== null) {
nextNode.prev = end;
}
}
current = current.next;
}
return head;
}
C#:
public class Solution {
/// <summary>
/// Flatten multilevel doubly linked list using recursion
/// Time: O(n)
/// Space: O(n) - recursion stack
/// </summary>
public Node FlattenRecursive(Node head) {
if (head == null) {
return head;
}
Node current = head;
while (current != null) {
if (current.child != null) {
// Recursively flatten child list
Node flattenedChild = FlattenRecursive(current.child);
// Store next node
Node nextNode = current.next;
// Connect current to flattened child
current.next = flattenedChild;
flattenedChild.prev = current;
current.child = null;
// Find end of flattened child
while (flattenedChild.next != null) {
flattenedChild = flattenedChild.next;
}
// Connect end of child to next node
flattenedChild.next = nextNode;
if (nextNode != null) {
nextNode.prev = flattenedChild;
}
}
current = current.next;
}
return head;
}
}
Key Insights
- Stack approach: Process child nodes when encountered, store next nodes for later
- Recursive approach: Flatten child lists recursively before connecting
- Doubly linked list: Maintain both next and prev pointers correctly
- Child pointer management: Set child to null after flattening
- Edge case handling: Handle empty lists and nodes without children
Edge Cases
- Empty list
- List with no children
- List with only children (no next nodes)
- Deeply nested child lists
- Single node list
Test Cases
# Test case 1: Normal case with children
# Original: 1->2->3->4->5->6
# | |
# 7->8 9->10
# | |
# 11 12
# Expected: 1->2->3->7->8->11->12->9->10->4->5->6
# Test case 2: Simple case
# Original: 1->2
# |
# 3
# Expected: 1->3->2
# Test case 3: No children
# Original: 1->2->3
# Expected: 1->2->3
Follow-up Questions
- How would you handle very deep nesting?
- Can you solve this with O(1) space?
- How would you handle cycles in child lists?
- What if you need to preserve the original structure?
Common Mistakes
- Not properly maintaining prev pointers
- Forgetting to set child to null after flattening
- Incorrect handling of next nodes when flattening
- Not considering empty child lists
- Memory leaks when not properly managing pointers
- Off-by-one errors in pointer connections