扁平化多级双向链表

430. 扁平化多级双向链表

难度中等264

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

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

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

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



扁平化后的链表如下图：

示例 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]

提示：

• 节点数目不超过 1000
• 1 <= Node.val <= 10^5

使用栈

开始遍历，遇到有孩子的节点开始遍历孩子链表，并使用栈保存当前的父链表的下一个节点，

遍历孩子链表完成后，将当前父链表的节点接到当前的子链表的后面

class Solution {
    public Node flatten(Node head) {
        
        Node dummyNode = new Node(0);
        dummyNode.next = head;

        Node pre = dummyNode;
        Node cur = head;
        solve(pre,cur);
        return dummyNode.next;
    }

    public void solve(Node pre,Node head){
        Node cur = head;
        Deque<Node> stack = new LinkedList<>();
        while(cur!=null||!stack.isEmpty()){
            if(cur!=null){
                if(cur.child!=null){
                    // 当前节点的下一个节点
                    Node nex = cur.next;
                    // 将当前节点的下一个节点加入到栈中去，如果孩子节点遍历完了，在把当前栈顶的节点追加到孩子链表的后面
                    stack.push(nex);
                    // 开始遍历他的孩子链表
                    cur.next = cur.child;
                    cur.child.prev = cur;
                    cur.child = null;
                }
                cur = cur.next;
                pre = pre.next;
            }else{
                // 孩子链表遍历完成，开始继续遍历父链表
                cur = stack.pop();
                // 将当前的父链表接到孩子链表的后面
                if(pre!=null) pre.next = cur;
                if(cur!=null) cur.prev = pre;
            }
        }
    }
}

赏

谢谢你请我吃糖果

微信