力扣学习笔记——430. 扁平化多级双向链表

解题思路

• 本题主要考验的是DFS（深度优先遍历）

懒了，自己拖着看吧。。。

图解：

实现代码

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        dfs(head);
        return head;
    }

    public Node dfs(Node node) {
        Node cur = node;
        // 记录链表最后一个节点
        Node last = null;

        while (cur != null) {
            Node next = cur.next;
            // 如果有子节点，首先处理子节点
            if (cur.child != null) {
                Node childLast = dfs(cur.child);

                next = cur.next;
                // 将 node 与 child 相连
                cur.next = cur.child;
                cur.child.prev = cur;

                // 如果 next 不为空，就将 last 与 next 相连
                if (next != null) {
                    childLast.next = next;
                    next.prev = childLast;
                }

                // 将 child 置空
                cur.child = null;
                last = childLast;
            } else {
                last = cur;
            }
            cur = next;
        }
        return last;
    }
}

复杂度分析

• 时间复杂度：O(N)
  • 遍历了整个链表的长度
• 空间复杂度：O(1)
  • 并没有递归链表长度，而是在有 child 节点的情况下遍历，因此一个是 O(1)