430. Flatten a Multilevel Doubly Linked List

Prompt

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. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

  • 1 <= Node.val <= 105

Approach

We can use the following example that they provide to demonstrate what approach would be ideal to solve this problem.

 1---2---3---4---5---6--NULL  [Level 0]
|
7---8---9---10--NULL [Level 1]
|
11--12--NULL [Level 2]

Code

Python | Time: O(n) where n = the total # of nodes | Space: O(n) where n = the total # of nodes

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

--

--

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
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com