Flatten a Multilevel Doubly Linked List

Advanced

Welcome, young Python coders! Today, your challenge is to flatten a multilevel doubly linked list. Imagine you have a peculiar list where each node might have a child node forming a hierarchy, like how a family tree spreads out with generations. Your job is to flatten this multi-layered list into a single-level list while maintaining the original order of nodes.

Your task is to write a function flatten() that takes a doubly linked list with potential child pointers and returns it as a flattened list.

How does a Node look like?

Each node in the doubly linked list might look something like this:

class Node: def __init__(self, val=None, prev=None, next=None, child=None): self.val = val self.prev = prev self.next = next self.child = child

Your Task

You're provided with the head of this doubly linked list. Your job is to traverse through each node and flatten the list by incorporating child nodes into the main line.

Example Execution

Let's visualize the process with the following inputs:

Imagine a linked list structured like this:

1 - 2 - 3
    |
    4 - 5

After flattening, it should look like:

1 - 2 - 4 - 5 - 3

Here's what your function calls should look like:

head = Node(1, next=Node(2, child=Node(4, next=Node(5)), next=Node(3))) flattened_head = flatten(head) # Function should return the head of the list in the order: 1 -> 2 -> 4 -> 5 -> 3

Note

  • Do not use any print statements; just return the altered list.
  • Think carefully about how you will manage the child pointers as you flatten the list.

How the tests work

Each test describes the list as nested val, next and child entries. The nodes are built for you, and the test checks the values you get by following next from the head you return.

Geek
Inputs

Arg 1:

{"val":1,"next":{"val":2,"child":{"val":4,"next":{"val":5}},"next":{"val":3}}}
Expected Output
[1, 2, 4, 5, 3]
Actual Output