LeetCode 430: Flatten a Multilevel Doubly Linked List Solution
Master LeetCode problem 430 (Flatten a Multilevel Doubly Linked List), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
430. Flatten a Multilevel Doubly Linked List
Problem Explanation
Explanation
To flatten a multilevel doubly linked list, we can use a stack to keep track of nodes with children. We start with the head node, and if a node has a child, we push its next node to the stack and connect the node to its child. We continue this process until all nodes have been flattened.
- Time Complexity: O(N) where N is the total number of nodes in the doubly linked list.
- Space Complexity: O(N) for the stack.
Solution Code
class Solution {
public Node flatten(Node head) {
if (head == null) return null;
Node current = head;
Stack<Node> stack = new Stack<>();
while (current != null) {
if (current.child != null) {
if (current.next != null) {
stack.push(current.next);
}
current.next = current.child;
current.next.prev = current;
current.child = null;
}
if (current.next == null && !stack.isEmpty()) {
current.next = stack.pop();
if (current.next != null) {
current.next.prev = current;
}
}
current = current.next;
}
return head;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 430 (Flatten a Multilevel Doubly Linked List)?
This page provides optimized solutions for LeetCode problem 430 (Flatten a Multilevel Doubly Linked List) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 430 (Flatten a Multilevel Doubly Linked List)?
The time complexity for LeetCode 430 (Flatten a Multilevel Doubly Linked List) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 430 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 430 in Java, C++, or Python.