题目

题目来源：力扣（LeetCode

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

示例 1：

输入：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]
解释：

输入的多级列表如下图所示：
image.png

扁平化后的链表如下图：
image.png

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

1—-2—-NULL
|
3—-NULL

示例 3：

输入：head = []
输出：[]

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

以 示例 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 的元素，以表示没有节点连接到上一级的上级节点。

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]
合并所有序列化结果，并去除末尾的 null 。

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

思路分析

递归 + 遍历链表

  1. 把多级地双向链表变成统一地单向链表，这个过程就是一个递归地过程。
  2. 遍历多级链表，遇到当前节点有孩子节点时，就将当前节点的子链表做扁平化处理，然后将扁平化后的子链表连接到当前节点上，与当前节点建立双向连接关系 ```javascript /**
    • // Definition for a Node.
    • function Node(val,prev,next,child) {
    • this.val = val;
    • this.prev = prev;
    • this.next = next;
    • this.child = child;
    • }; */

/**

  • @param {Node} head
  • @return {Node} */

var flatten = function(head) { if (head == null) return null; // 定义 curr 指针指向 当前节点 let curr = head; // next 存储的是 curr 指针指向的节点的下一个节点 let next; // temp 是扁平化之后的子链表 let temp;

  1. while(curr) {
  2.   temp = null;
  3.   if (curr.child) {
  4.     // 当前节点有孩子节点，则将孩子节点扁平化处理，存到 temp 里
  5.     temp = flatten(curr.child);
  6.     // 扁平化 curr.child 指针所指向的链表以后，删除 child 指针，因为最终不再需要改指针
  7.     curr.child = null;
  8.     // 复制 curr.next 指针存储到 next 里，因为接下来要将curr.next 指向扁平化后的链表
  9.     next = curr.next;
  11.     // 当前节点和扁平化后的链表建立双向连接
  13.     curr.next = temp; // 将 curr.next 指向扁平化后的链表
  14.     temp.prev = curr; // 将 扁平化后链表的第一个节点的 prev 指针指向当前节点
  16.     // 让 curr 指针顺着扁平化后的链表走到最后一位，拿到扁平化后的链表的尾节点
  17.     while(curr.next) curr = curr.next;
  18.     // 将扁平化后链表的尾节点的 next 指针指向当前有孩子节点的节点的下一个节点
  19.     curr.next = next;
  21.     // 把有孩子节点的节点的 prev 指针指向扁平化后链表的尾节点，让扁平化后的链表与当前有孩子节点的节点的下一个节点建立双向连接
  22.     if (next) next.prev = curr;
  23.   }
  24.   // 将 curr 指针指向当前节点的下一个节点，继续遍历节点 
  25.   curr = curr.next;
  26. }
  27. return head;

};

  3. **递归 + 寻找尾部节点**
  5. 1. 尾部节点的定义：当一个节点既无child节点又没有next节点时，称该节点为尾部节点.
  6. 1. 理解题意，对于每一个拥有child节点的节点，扁平化列表只会对四个节点进行操作，该节点本身，该节点的next节点，该节点的child节点以及child节点的尾部节点.
  7. 1. 这四个节点中，只有child节点的尾部节点是我们没办法直接获取的，因此，对于每一个拥有child节点的节点，我们进行其child节点的尾部节点的搜索，完成搜索后，动态的改变链表的结构，即对于四个节点进行操作，由于所用的递归，所以修改之后的表现形式（即链表的变化）是自底向上的，我们逐层获取尾部节点并动态的修改链表，当第一层所有含有child节点的节点被操作完毕后，链表的扁平化就完成了.
  8. 1. 四个节点的操作见注释.
  9. ```javascript
  12. var flatten = function (head) {
  13.     // 首先保存 head 节点，因为函数最后的返回值作为第一层的最后一个节点
  14.     const root = head;
  15.     // 进行尾部节点的搜索并动态的修改链表结构
  16.     findEnd(head);
  17.     return root;
  19.     function findEnd(head) {
  20.         // head 为 null 时则直接返回 null
  21.         if (head == null) return null;
  23.         // 当前节点既无 child 节点，又没有 next节点时，该节点为尾部节点，找到了尾部节点，将其返回
  24.         if (head.child == null && head.next == null) return head;
  26.         // 当前节点有 child 节点，对child节点进行扁平化处理
  27.         if (head.child != null) {
  28.             // 找到了下一层链表(子链表)的尾部节点，此时子链表已经完成了扁平化
  29.             const end = findEnd(head.child);
  30.             // 将子链表的尾部节点的 next 指向当前节点(当前有孩子节点的节点)的 next
  31.             end.next = head.next;
  32.             // 当前节点为 null 时，无需进行回连
  33.             if (head.next != null) head.next.prev = end;
  34.             // child 节点变为 当前节点的 next 节点，即将子链表连接到当前节点的 next 指针上
  35.             head.next = head.child;
  36.             //  child 节点会连，将 child 节点的prev 指向指向当前节点(当前有孩子节点的节点)，使child 节点与当前节点形成双向连接
  37.             head.child.prev = head;
  38.             // 扁平化 curr.child 指针所指向的链表以后，删除 child 指针，因为最终不再需要改指针
  39.             head.child = null;
  41.             //此时该层已经完成扁平化，从end节点继续寻找尾部节点
  42.             //不能从end.next节点寻找的理由是end节点可能已经是当前层的尾部节点了，end.next可能是一个空节点与尾部节点一定不为空矛盾
  43.             //例：
  44.             //1 -> null
  45.             //2 -> null
  46.             //3 -> null
  48.             //head.child的尾部节点也是head的尾部节点
  49.             return findEnd(end)
  50.         }
  51.         //当前节点无child节点，直接进入next节点
  52.         return findEnd(head.next)
  53.     }
  55. };