文章目录题目标题和出处难度题目描述要求示例数据范围如何表示测试用例中的多级链表解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目标题和出处标题扁平化多级双向链表出处430. 扁平化多级双向链表难度7 级题目描述要求给定一个双链表其中的每个结点有一个后指针、一个前指针和一个额外的子指针。这个子指针可能指向一个单独的双向链表也包含这些特殊的结点。这些子列表可以有一个或多个自己的子列表以此类推以生成如下面的示例所示的多层数据结构。给定链表的头结点head \texttt{head}head将链表扁平化以便所有结点都出现在单层双链表中。用curr \texttt{curr}curr表示一个带有子列表的结点。子列表中的结点应该出现在扁平化列表中的curr \texttt{curr}curr之后和curr.next \texttt{curr.next}curr.next之前。返回扁平列表的头结点。列表中的结点必须将其所有子指针设为空。示例示例 1输入head [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] \texttt{head [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]}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] \texttt{[1,2,3,7,8,11,12,9,10,4,5,6]}[1,2,3,7,8,11,12,9,10,4,5,6]解释输入的多级列表如上图所示。扁平化后的链表如下图示例 2输入head [1,2,null,3] \texttt{head [1,2,null,3]}head [1,2,null,3]输出[1,3,2] \texttt{[1,3,2]}[1,3,2]解释输入的多级列表如上图所示。扁平化后的链表如下图示例 3输入head [] \texttt{head []}head []输出[] \texttt{[]}[]说明输入中可能存在空列表。数据范围结点数目不超过1000 \texttt{1000}10001 ≤ Node.val ≤ 10 5 \texttt{1} \le \texttt{Node.val} \le \texttt{10}^\texttt{5}1≤Node.val≤105如何表示测试用例中的多级链表以示例 1为例1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULL序列化其中的每一级之后[1,2,3,4,5,6,null] [7,8,9,10,null] [11,12,null]为了将每一级都序列化到同一个输入在每一级添加值为null \texttt{null}null的元素以表示没有结点连接到上一级的上级结点。[1, 2, 3, 4, 5, 6, null] | [null, null, 7, 8, 9, 10, null] | [ null, 11, 12, null]合并所有序列化结果并去除末尾的null \texttt{null}null得到序列化结果[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]解法一思路和算法双向链表中的每个结点分别有三个指针后指针、前指针和子指针将这三个指针指向的结点分别称为后结点、前结点和子结点。双向链表的扁平化操作发生在子结点不为空的结点处。将结点node \textit{node}node的后结点记为next \textit{next}next子结点记为child \textit{child}child当child \textit{child}child不为空时扁平化的做法是将以child \textit{child}child为头结点的双向链表扁平化将扁平化后的双向链表置于node \textit{node}node和next \textit{next}next之间。上述过程是递归的过程可以使用深度优先搜索实现。定义深度优先搜索的方法当给定双向链表的头结点时该方法将双向链表扁平化并返回扁平化后的双向链表的尾结点。具体做法是从头结点开始依次遍历双向链表中的每个结点遍历过程中维护尾结点tail \textit{tail}tail对于遍历到的结点curr \textit{curr}curr执行如下操作。将curr \textit{curr}curr的子结点记为child \textit{child}child。判断child \textit{child}child是否为空执行相应的操作。如果child \textit{child}child不为空则对child \textit{child}child递归调用扁平化将返回值记为childTail \textit{childTail}childTail返回值为以child \textit{child}child为头结点的双向链表的尾结点将next \textit{next}next拼接到childTail \textit{childTail}childTail的后面将curr \textit{curr}curr的子结点设为空将tail \textit{tail}tail更新为childTail \textit{childTail}childTail。如果child \textit{child}child为空则将tail \textit{tail}tail更新为curr \textit{curr}curr。将curr \textit{curr}curr移动到tail \textit{tail}tail的后结点处。遍历结束时整个双向链表完成扁平化返回头结点。遍历过程中由于每次更新curr \textit{curr}curr时都是将curr \textit{curr}curr移动到tail \textit{tail}tail的后结点处因此每个结点只访问一次。实现方面将双向链表中的两个结点连接为前后结点时需要分别更新前结点的后指针和后结点的前指针。例如将结点A AA的后结点更新为结点B BB需要执行如下操作。将结点A AA的后指针指向结点B BB。判断结点B BB是否为空如果结点B BB不为空将结点B BB的前指针指向结点A AA。考虑示例 1 的双向链表。初始时有3 33层从上到下分别是第1 11层到第3 33层括号中的数字表示子结点。[ 1 , 2 , 3 ( 7 ) , 4 , 5 , 6 ] [ 7 , 8 ( 11 ) , 9 , 10 ] [ 11 , 12 ] \begin{aligned} [1, 2, 3(7), 4, 5, 6] \\ [7, 8(11), 9, 10] \\ [11, 12] \end{aligned}[1,2,3(7),4,5,6][7,8(11),9,10][11,12]将第3 33层的双向链表置于第2 22层的8 88和9 99之间完成第2 22层的扁平化。[ 1 , 2 , 3 ( 7 ) , 4 , 5 , 6 ] [ 7 , 8 , 11 , 12 , 9 , 10 ] \begin{aligned} [1, 2, 3(7), 4, 5, 6] \\ [7, 8, 11, 12, 9, 10] \end{aligned}[1,2,3(7),4,5,6][7,8,11,12,9,10]将第2 22层的双向链表置于第1 11层的3 33和4 44之间完成整个双向链表的扁平化。[ 1 , 2 , 3 , 7 , 8 , 11 , 12 , 9 , 10 , 4 , 5 , 6 ] [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6][1,2,3,7,8,11,12,9,10,4,5,6]代码classSolution{publicNodeflatten(Nodehead){dfs(head);returnhead;}publicNodedfs(Nodenode){Nodecurrnode;Nodetailnull;while(curr!null){Nodechildcurr.child;if(child!null){Nodenextcurr.next;NodechildTaildfs(child);curr.nextchild;child.prevcurr;if(next!null){childTail.nextnext;next.prevchildTail;}curr.childnull;tailchildTail;}else{tailcurr;}currtail.next;}returntail;}}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是双向链表的结点数。遍历每个结点一次每个结点的操作时间是O ( 1 ) O(1)O(1)。空间复杂度O ( n ) O(n)O(n)其中n nn是双向链表的结点数。空间复杂度主要是递归调用的栈空间取决于双向链表的层数最差情况下双向链表的层数是O ( n ) O(n)O(n)。解法二思路和算法也可以使用迭代实现扁平化双向链表迭代实现需要使用显性栈。从头结点开始依次遍历双向链表中的每个结点对于遍历到的结点curr \textit{curr}curr执行如下操作。将curr \textit{curr}curr的子结点记为child \textit{child}child。如果child \textit{child}child不为空执行如下操作。如果curr \textit{curr}curr的后结点不为空则将curr \textit{curr}curr的后结点入栈。将child \textit{child}child拼接到curr \textit{curr}curr的后面将curr \textit{curr}curr的子结点设为空。如果curr \textit{curr}curr的后结点为空且栈不为空则将一个结点出栈将出栈结点拼接到curr \textit{curr}curr的后面。将curr \textit{curr}curr移动到其后结点处。遍历结束时整个双向链表完成扁平化返回头结点。遍历过程中每个结点只访问一次。代码classSolution{publicNodeflatten(Nodehead){DequeNodestacknewArrayDequeNode();Nodecurrhead;while(curr!null){Nodechildcurr.child;if(child!null){if(curr.next!null){stack.push(curr.next);}curr.nextchild;child.prevcurr;curr.childnull;}if(curr.nextnull!stack.isEmpty()){Nodenextstack.pop();curr.nextnext;next.prevcurr;}currcurr.next;}returnhead;}}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是双向链表的结点数。遍历每个结点一次每个结点的操作时间是O ( 1 ) O(1)O(1)。空间复杂度O ( n ) O(n)O(n)其中n nn是双向链表的结点数。空间复杂度主要是栈空间取决于双向链表的层数最差情况下双向链表的层数是O ( n ) O(n)O(n)。
搜索题目：扁平化多级双向链表
文章目录题目标题和出处难度题目描述要求示例数据范围如何表示测试用例中的多级链表解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目标题和出处标题扁平化多级双向链表出处430. 扁平化多级双向链表难度7 级题目描述要求给定一个双链表其中的每个结点有一个后指针、一个前指针和一个额外的子指针。这个子指针可能指向一个单独的双向链表也包含这些特殊的结点。这些子列表可以有一个或多个自己的子列表以此类推以生成如下面的示例所示的多层数据结构。给定链表的头结点head \texttt{head}head将链表扁平化以便所有结点都出现在单层双链表中。用curr \texttt{curr}curr表示一个带有子列表的结点。子列表中的结点应该出现在扁平化列表中的curr \texttt{curr}curr之后和curr.next \texttt{curr.next}curr.next之前。返回扁平列表的头结点。列表中的结点必须将其所有子指针设为空。示例示例 1输入head [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] \texttt{head [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]}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] \texttt{[1,2,3,7,8,11,12,9,10,4,5,6]}[1,2,3,7,8,11,12,9,10,4,5,6]解释输入的多级列表如上图所示。扁平化后的链表如下图示例 2输入head [1,2,null,3] \texttt{head [1,2,null,3]}head [1,2,null,3]输出[1,3,2] \texttt{[1,3,2]}[1,3,2]解释输入的多级列表如上图所示。扁平化后的链表如下图示例 3输入head [] \texttt{head []}head []输出[] \texttt{[]}[]说明输入中可能存在空列表。数据范围结点数目不超过1000 \texttt{1000}10001 ≤ Node.val ≤ 10 5 \texttt{1} \le \texttt{Node.val} \le \texttt{10}^\texttt{5}1≤Node.val≤105如何表示测试用例中的多级链表以示例 1为例1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULL序列化其中的每一级之后[1,2,3,4,5,6,null] [7,8,9,10,null] [11,12,null]为了将每一级都序列化到同一个输入在每一级添加值为null \texttt{null}null的元素以表示没有结点连接到上一级的上级结点。[1, 2, 3, 4, 5, 6, null] | [null, null, 7, 8, 9, 10, null] | [ null, 11, 12, null]合并所有序列化结果并去除末尾的null \texttt{null}null得到序列化结果[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]解法一思路和算法双向链表中的每个结点分别有三个指针后指针、前指针和子指针将这三个指针指向的结点分别称为后结点、前结点和子结点。双向链表的扁平化操作发生在子结点不为空的结点处。将结点node \textit{node}node的后结点记为next \textit{next}next子结点记为child \textit{child}child当child \textit{child}child不为空时扁平化的做法是将以child \textit{child}child为头结点的双向链表扁平化将扁平化后的双向链表置于node \textit{node}node和next \textit{next}next之间。上述过程是递归的过程可以使用深度优先搜索实现。定义深度优先搜索的方法当给定双向链表的头结点时该方法将双向链表扁平化并返回扁平化后的双向链表的尾结点。具体做法是从头结点开始依次遍历双向链表中的每个结点遍历过程中维护尾结点tail \textit{tail}tail对于遍历到的结点curr \textit{curr}curr执行如下操作。将curr \textit{curr}curr的子结点记为child \textit{child}child。判断child \textit{child}child是否为空执行相应的操作。如果child \textit{child}child不为空则对child \textit{child}child递归调用扁平化将返回值记为childTail \textit{childTail}childTail返回值为以child \textit{child}child为头结点的双向链表的尾结点将next \textit{next}next拼接到childTail \textit{childTail}childTail的后面将curr \textit{curr}curr的子结点设为空将tail \textit{tail}tail更新为childTail \textit{childTail}childTail。如果child \textit{child}child为空则将tail \textit{tail}tail更新为curr \textit{curr}curr。将curr \textit{curr}curr移动到tail \textit{tail}tail的后结点处。遍历结束时整个双向链表完成扁平化返回头结点。遍历过程中由于每次更新curr \textit{curr}curr时都是将curr \textit{curr}curr移动到tail \textit{tail}tail的后结点处因此每个结点只访问一次。实现方面将双向链表中的两个结点连接为前后结点时需要分别更新前结点的后指针和后结点的前指针。例如将结点A AA的后结点更新为结点B BB需要执行如下操作。将结点A AA的后指针指向结点B BB。判断结点B BB是否为空如果结点B BB不为空将结点B BB的前指针指向结点A AA。考虑示例 1 的双向链表。初始时有3 33层从上到下分别是第1 11层到第3 33层括号中的数字表示子结点。[ 1 , 2 , 3 ( 7 ) , 4 , 5 , 6 ] [ 7 , 8 ( 11 ) , 9 , 10 ] [ 11 , 12 ] \begin{aligned} [1, 2, 3(7), 4, 5, 6] \\ [7, 8(11), 9, 10] \\ [11, 12] \end{aligned}[1,2,3(7),4,5,6][7,8(11),9,10][11,12]将第3 33层的双向链表置于第2 22层的8 88和9 99之间完成第2 22层的扁平化。[ 1 , 2 , 3 ( 7 ) , 4 , 5 , 6 ] [ 7 , 8 , 11 , 12 , 9 , 10 ] \begin{aligned} [1, 2, 3(7), 4, 5, 6] \\ [7, 8, 11, 12, 9, 10] \end{aligned}[1,2,3(7),4,5,6][7,8,11,12,9,10]将第2 22层的双向链表置于第1 11层的3 33和4 44之间完成整个双向链表的扁平化。[ 1 , 2 , 3 , 7 , 8 , 11 , 12 , 9 , 10 , 4 , 5 , 6 ] [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6][1,2,3,7,8,11,12,9,10,4,5,6]代码classSolution{publicNodeflatten(Nodehead){dfs(head);returnhead;}publicNodedfs(Nodenode){Nodecurrnode;Nodetailnull;while(curr!null){Nodechildcurr.child;if(child!null){Nodenextcurr.next;NodechildTaildfs(child);curr.nextchild;child.prevcurr;if(next!null){childTail.nextnext;next.prevchildTail;}curr.childnull;tailchildTail;}else{tailcurr;}currtail.next;}returntail;}}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是双向链表的结点数。遍历每个结点一次每个结点的操作时间是O ( 1 ) O(1)O(1)。空间复杂度O ( n ) O(n)O(n)其中n nn是双向链表的结点数。空间复杂度主要是递归调用的栈空间取决于双向链表的层数最差情况下双向链表的层数是O ( n ) O(n)O(n)。解法二思路和算法也可以使用迭代实现扁平化双向链表迭代实现需要使用显性栈。从头结点开始依次遍历双向链表中的每个结点对于遍历到的结点curr \textit{curr}curr执行如下操作。将curr \textit{curr}curr的子结点记为child \textit{child}child。如果child \textit{child}child不为空执行如下操作。如果curr \textit{curr}curr的后结点不为空则将curr \textit{curr}curr的后结点入栈。将child \textit{child}child拼接到curr \textit{curr}curr的后面将curr \textit{curr}curr的子结点设为空。如果curr \textit{curr}curr的后结点为空且栈不为空则将一个结点出栈将出栈结点拼接到curr \textit{curr}curr的后面。将curr \textit{curr}curr移动到其后结点处。遍历结束时整个双向链表完成扁平化返回头结点。遍历过程中每个结点只访问一次。代码classSolution{publicNodeflatten(Nodehead){DequeNodestacknewArrayDequeNode();Nodecurrhead;while(curr!null){Nodechildcurr.child;if(child!null){if(curr.next!null){stack.push(curr.next);}curr.nextchild;child.prevcurr;curr.childnull;}if(curr.nextnull!stack.isEmpty()){Nodenextstack.pop();curr.nextnext;next.prevcurr;}currcurr.next;}returnhead;}}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是双向链表的结点数。遍历每个结点一次每个结点的操作时间是O ( 1 ) O(1)O(1)。空间复杂度O ( n ) O(n)O(n)其中n nn是双向链表的结点数。空间复杂度主要是栈空间取决于双向链表的层数最差情况下双向链表的层数是O ( n ) O(n)O(n)。
