package g0401_0500.s0430_flatten_a_multilevel_doubly_linked_list;

@SuppressWarnings("java:S1104")

public class Node {

public int val;

public Node prev;

public Node next;

public Node child;

public Node(int val) {

this.val = val;

}

@Override

public String toString() {

return "Node{" + "val=" + val + ",next=" + next + "}";

}

}

package g0401_0500.s0430_flatten_a_multilevel_doubly_linked_list;

public class Solution {

// is true ONLY for the first element of the list

private boolean first = true;

// Holds the head node of the newly constructed doubly linked list

private Node root;

// Holds the current node of the newly constructed doubly linked list

private Node current;

public Node flatten(Node head) {

if (head == null) {

return root;

} else {

// Construct our doubly linked list

if (first) {

first = !first;

root = new Node(head.val);

current = root;

} else {

// Map all values to the newly constructed list.

// temp value to hold our prev element

Node temp = current;

current.next = new Node(head.val);

current = current.next;

current.prev = temp;

}

}

// iterate over child nodes.

if (head.child != null) {

flatten(head.child);

}

if (head.next != null) {

// iterate next

flatten(head.next);

}

return root;

}

}

430\. Flatten a Multilevel Doubly Linked List

Medium

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.

Given the `head` of the first level of the list, **flatten** the list so that all the nodes appear in a single-level, doubly linked list. Let `curr` be a node with a child list. The nodes in the child list should appear **after** `curr` and **before** `curr.next` in the flattened list.

Return _the_ `head` _of the flattened list. The nodes in the list must have **all** of their child pointers set to_ `null`.

**Example 1:**

**Input:** head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

**Output:** [1,2,3,7,8,11,12,9,10,4,5,6]

**Explanation:** The multilevel linked list in the input is shown. After flattening the multilevel linked list it becomes: 

**Example 2:**

**Input:** head = [1,2,null,3]

**Output:** [1,3,2]

**Explanation:**

The multilevel linked list in the input is shown.

After flattening the multilevel linked list it becomes:


**Example 3:**

**Input:** head = []

**Output:** []

**Explanation:** There could be empty list in the input.

**Constraints:**

* The number of Nodes will not exceed `1000`.

* <code>1 <= Node.val <= 10⁵</code>

**How the multilevel linked list is represented in test cases:**

We use the multilevel linked list from **Example 1** above:

1---2---3---4---5---6--NULL

|

7---8---9---10--NULL

|

11--12--NULL

The serialization of each level is as follows:

[1,2,3,4,5,6,null]

[7,8,9,10,null]

[11,12,null]

To serialize all levels together, we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

[1, 2, 3, 4, 5, 6, null]

|

[null, null, 7, 8, 9, 10, null]

|

[ null, 11, 12, null]

Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

package g0401_0500.s0430_flatten_a_multilevel_doubly_linked_list;

import static org.hamcrest.CoreMatchers.equalTo;

import static org.hamcrest.MatcherAssert.assertThat;

import org.junit.jupiter.api.Test;

class SolutionTest {

@Test

void flatten() {

Node node1 = new Node(1);

Node node2 = new Node(2);

node1.next = node2;

node2.prev = node1;

Node node3 = new Node(3);

node2.next = node3;

node3.prev = node2;

Node node4 = new Node(4);

node3.next = node4;

node4.prev = node3;

Node node5 = new Node(5);

node4.next = node5;

node5.prev = node4;

Node node6 = new Node(6);

node5.next = node6;

node6.prev = node5;

Node node7 = new Node(7);

node3.child = node7;

Node node8 = new Node(8);

node7.next = node8;

node8.prev = node7;

Node node9 = new Node(9);

node8.next = node9;

node9.prev = node8;

Node node10 = new Node(10);

node9.next = node10;

node10.prev = node9;

Node node11 = new Node(11);

node8.child = node11;

Node node12 = new Node(12);

node11.next = node12;

node12.prev = node11;

assertThat(

new Solution().flatten(node1).toString(),

equalTo(

"Node{val=1,next=Node{"

+ "val=2,next=Node{val=3,next=Node{val=7,next=Node{val=8,next=Node{val=11,next="

+ "Node{val=12,next=Node{val=9,next=Node{val=10,next=Node{val=4,next=Node{val=5"

+ ",next=Node{val=6,next=null}}}}}}}}}}}}"));

}

}