flatten-a-multilevel-doubly-linked-list

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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 <code>head</code> of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let <code>curr</code> be a node with a child list. The nodes in the child list should appear after <code>curr</code> and before <code>curr.next</code> in the flattened list.

Return the <code>head</code> of the flattened list. The nodes in the list must have all of their child pointers set to <code>null</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/09/flatten11.jpg" style="width: 700px; height: 339px;" />
<pre>
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:
<img src="https://assets.leetcode.com/uploads/2021/11/09/flatten12.jpg" style="width: 1000px; height: 69px;" />
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/09/flatten2.1jpg" style="width: 200px; height: 200px;" />
<pre>
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:
<img src="https://assets.leetcode.com/uploads/2021/11/24/list.jpg" style="width: 300px; height: 87px;" />
</pre>

Example 3:

<pre>
Input: head = []
Output: []
Explanation: There could be empty list in the input.
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of Nodes will not exceed <code>1000</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 105</code></li>
</ul>

&nbsp;
How the multilevel linked list is represented in test cases:

We use the multilevel linked list from Example 1 above:

<pre>
 1---2---3---4---5---6--NULL
 |
 7---8---9---10--NULL
 |
 11--12--NULL</pre>

The serialization of each level is as follows:

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

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:

<pre>
[1, 2, 3, 4, 5, 6, null]
 |
[null, null, 7, 8, 9, 10, null]
 |
[ null, 11, 12, null]
</pre>

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

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

flatten

Flatten a Multilevel Doubly Linked List

Flatten Binary Tree to Linked List

flatten-binary-tree-to-linked-list

二叉树展开为链表

Correct a Binary Tree

correct-a-binary-tree

纠正二叉树

Depth-First Search

Linked List

Doubly-Linked List

你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。

给定链表的头节点&nbsp;head&nbsp;，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 <code>curr</code> 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的&nbsp;<code>curr</code> 之后 和&nbsp;<code>curr.next</code>&nbsp;之前 。

返回 扁平列表的 <code>head</code>&nbsp;。列表中的节点必须将其 所有 子指针设置为&nbsp;<code>null</code>&nbsp;。

&nbsp;

示例 1：

<img src="https://assets.leetcode.com/uploads/2021/11/09/flatten11.jpg" style="height:339px; width:700px" />

<pre>
输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：输入的多级列表如上图所示。
扁平化后的链表如下图：
<img src="https://assets.leetcode.com/uploads/2021/11/09/flatten12.jpg" style="height:69px; width:1000px" />
</pre>

示例 2：

<img src="https://assets.leetcode.com/uploads/2021/11/09/flatten2.1jpg" style="height:200px; width:200px" />

<pre>
输入：head = [1,2,null,3]
输出：[1,3,2]
解释：输入的多级列表如上图所示。
扁平化后的链表如下图：
<img src="https://assets.leetcode.com/uploads/2021/11/24/list.jpg" style="height:87px; width:300px" />
</pre>

示例 3：

<pre>
输入：head = []
输出：[]
说明：输入中可能存在空列表。
</pre>

&nbsp;

提示：

<ul>
	<li>节点数目不超过 <code>1000</code></li>
	<li><code>1 &lt;= Node.val &lt;= 105</code></li>
</ul>

&nbsp;

如何表示测试用例中的多级链表？

以 示例 1 为例：

<pre>
 1---2---3---4---5---6--NULL
 |
 7---8---9---10--NULL
 |
 11--12--NULL</pre>

序列化其中的每一级之后：

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

为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。

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

合并所有序列化结果，并去除末尾的 null 。

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

<ul>
</ul>