一、题目

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

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

点击查看原题
难度级别： 中等

二、思路

1）DFS

优先遍历孩子链表，将next链表链接在孩子链表尾部
使用dfs函数，认为dfs函数会返回该链表的尾部节点，拿到尾部链表节点后，插入在当前遍历节点cur和cur.next中间即可

三、代码

1）DFS

  1. class Solution {
  2.     public Node flatten(Node head) {
  3.         dfs(head);
  4.         return head;
  5.     }
  6.     public Node dfs(Node head) {
  7.         Node cur = head, last = head;    // 当前遍历的节点cur，当前链表的尾节点last
  8.         while (cur != null) {
  9.             if (cur.child != null) {
  10.                 Node childLast = dfs(cur.child);    // 获取孩子节点的尾节点
  11.                 Node childHead = cur.child;
  12.                 cur.child = null;
  13.                 if (cur.next != null) {    // 链接孩子尾部节点和cur.next节点
  14.                     childLast.next = cur.next;
  15.                     cur.next.prev = childLast;
  16.                 }
  17.                 cur.next = childHead;    // 链接cur节点和孩子头节点
  18.                 childHead.prev = cur;
  19.                 cur = childLast;
  20.             }
  21.             last = cur;
  22.             cur = cur.next;
  23.         }
  24.         return last;
  25.     }
  26. }
  1. 时间复杂度为`O(n)`，假设最深孩子深度为`m`，空间复杂度为`O(m)`