通关剑指 Offer——剑指 Offer II 028. 展平多级双向链表

1.题目描述

剑指 Offer II 028. 展平多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

示例 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]
解释：
1
2
3

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

扁平化后的链表如下图：

示例 2：

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

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

  1---2---NULL
  |
  3---NULL
1
2
3
4
5
6
7
8
9

示例 3：

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

2.解题思路与代码

2.1 解题思路

题目给的双向链表结构中增加了 child 变量，并且需要将有 child 变量的节点的 next 指向 child，child 的 prev 指向当前节点，然后将子链表的最后一个节点的 next 指向当前节点的 next，当前节点的 next 节点的 prev 指向子链表的最后一位，如下图所示：

在理清楚需求之后我们就需要分析双向链表的操作，这里需要两步操作：

• 有子链表的节点与子链表的头节点进行连接
• 子链表的最后一个节点与当前节点原本的 next 节点进行连接

针对第一步的操作，我们可以直接改变当前节点的 next 和子链表头节点的 prev 即可，同时断掉当前节点的 child，即

head.next = head.child;
head.child.prev = head;
head.child = null;
1
2
3

这里需要注意题目规定子链表中的节点也可以有自己的子链表，如示例一所示。所以这里需要先使用递归来对子链表进行处理，在递归的时候，如果节点的 child 不为空，那么连接节点和子链表并且继续往下递归。这样就能够将所有层级的节点与子链表头部连接完成。
针对第二步，我们就需要先拿到提取出当前节点 next 节点，然后在子链表遍历完成之后将子链表的最后一个节点和原 next 节点连接即可。由于是在递归的对子链表进行处理，因此选用一个栈来缓存拥有子节点的 next 节点，以示例一为例，当我们遍历到 3 这个节点时，将 3 的 next 节点 4 放入栈中

然后开始向下一层递归，当遍历到节点 8 时，此时 8 节点拥有子链表，那么我们将 8 的 next 节点 9 节点放入栈中，然后继续递归进入下一层

这时最后一层遍历完毕之后需要将最后一个节点 12 与上一层的 8 节点的 next 节点进行连接，于是从栈中弹出栈顶元素，然后将 12 节点与 9 节点进行连接，同理节点 3 的子链表遍历完成后弹出栈顶元素 4，将子链表最后一个节点 10 与 4 连接即可。

Node pop = pre.pop();
head.next = pop;
pop.prev = head;
1
2
3

2.2 代码

class Solution {
    Stack<Node> pre = new Stack<>();

    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }
        Node curr = head;
        while (curr != null) {
            process(curr);
            curr = curr.next;
        }
        return head;
    }

    public void process(Node head) {
        if (head.next == null && head.child == null) {
            if (!pre.isEmpty()) {
                // 链表最后一个节点与上层 next 节点连接
                Node pop = pre.pop();
                head.next = pop;
                pop.prev = head;
            }
            return;
        }
        if (head.child != null) {
            if (head.next != null) {
                pre.push(head.next);
            }
            // 当前节点与子链表第一个节点连接
            head.next = head.child;
            head.child.prev = head;
            head.child = null;
        }
        process(head.next);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

2.3 测试结果

通过测试

3.总结

• 使用递归对每一层链表进行操作
• 主要操作有子链表的节点与子链表连接、子链表最后一个节点与上层 next 节点连接
• 由于递归本身就是一个栈操作，因此可以对代码进行优化去掉栈