Highlights
- Linked List
- A stack implementation of DFS to search for the deepest node
Goal
- Flatten a multi-level linked list that is nested in [parent → next → child] format
- Instead of nested with the children, flatten the LL and transform to a [parent → next] format
Method
- Use the classic stack to perform a DFS style traversal: to handle the child first
- reassign the prev, next, and child property during each iteration
Time & Space
- Time: we are traversing the LL once → O(N)
- Space: we are creating a new LL with the same number of elements → O(N)
Code
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':
if not head:
return head
stack = [head]
l = Node()
res = l
while stack:
current = stack.pop()
if current.next:
stack.append(current.next)
if current.child:
stack.append(current.child)
current.prev = l
current.child = None
l.next = current
l = l.next
res.next.prev = None
return res.next
