[LL] LC 430. Flatten a Multilevel Doubly Linked List


  • Linked List
  • A stack implementation of DFS to search for the deepest node


  • 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


  • 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)


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:
if current.child:

current.prev = l
current.child = None
l.next = current
l = l.next

res.next.prev = None
return res.next




Data Engineering & Analytics

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Iris S

Iris S

Data Engineering & Analytics

More from Medium