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

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

--

--

--

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