leetcode430-扁平化多级双向链表

原题

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

扁平化列表,使所有结点出现在单级双链表中。您将获得列表第一级的头部。

示例:

输入:
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL

输出:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

以上示例的说明:

给出以下多级双向链表:

leetcode430-扁平化多级双向链表

我们应该返回如下所示的扁平双向链表:

leetcode430-扁平化多级双向链表

解法

思想

深度优先搜索,将每次最后一个搜索到节点记录下来,回溯的时候能继续附加在上一个节点之后。

代码

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/
class Solution {
    Node pre = null;
    public Node flatten(Node head) {
        dfs(head);
        return head;
    }

    public void dfs(Node node){
        if(node==null) return;
        Node child = node.child;
        Node next = node.next;
        node.child = null;
        if(pre != null){
            pre.next = node;
            node.prev = pre;
        }
        pre = node;
        dfs(child);
        dfs(next);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode430-%e6%89%81%e5%b9%b3%e5%8c%96%e5%a4%9a%e7%ba%a7%e5%8f%8c%e5%90%91%e9%93%be%e8%a1%a8/

发表评论

电子邮件地址不会被公开。