MediumNo. 0430
Flatten a Multilevel Doubly Linked List — LeetCode 430 Python Solution
- Pattern
- Linked List
- Topics
- Depth-First Search, Linked List, Doubly-Linked List
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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.
Example
- 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]
- Explanation
- The multilevel linked list in the input is shown.
Python solution
"""
# 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: 'Node') -> 'Node':
def preorder(pre, cur):
if cur is None:
return pre
cur.prev = pre
pre.next = cur
t = cur.next
tail = preorder(cur, cur.child)
cur.child = None
return preorder(tail, t)
if head is None:
return None
dummy = Node(0, None, head, None)
preorder(dummy, head)
dummy.next.prev = None
return dummy.nextComplexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 430. Flatten a Multilevel Doubly Linked List is filed here because LeetCode tags it Linked List and Doubly-Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0116 | Populating Next Right Pointers in Each Node | Medium |
| 0117 | Populating Next Right Pointers in Each Node II | Medium |
| 1367 | Linked List in Binary Tree | Medium |
| 0437 | Path Sum III | Medium |
| 0098 | Validate Binary Search Tree | Medium |
| 0099 | Recover Binary Search Tree | Medium |
Frequently asked questions
- How hard is LeetCode 430. Flatten a Multilevel Doubly Linked List?
LeetCode 430. Flatten a Multilevel Doubly Linked List is rated Medium on LeetCode.
- What is the time complexity of LeetCode 430. Flatten a Multilevel Doubly Linked List?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 430. Flatten a Multilevel Doubly Linked List?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 430. Flatten a Multilevel Doubly Linked List cover?
LeetCode 430. Flatten a Multilevel Doubly Linked List is tagged Depth-First Search, Linked List and Doubly-Linked List on LeetCode.