题目: 多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
示例 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] 解释：
输入的多级列表如下图所示： 扁平化后的链表如下图： 解题思路: 说不清, 照着代码画图理解
/* // 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) { if(head == null) return head; head = dfs(head); head.prev = null; return head; } private Node dfs(Node head) { if(head == null) return null; Node cur = head; while(cur != null){ head.prev = cur; Node next = cur.next; if(cur.child != null){ Node h = dfs(cur.child); Node t = h.prev; //获得该一级的尾节点 cur.child = null; h.prev = cur; //更改子节点的prev指向合并链表 cur.next = h; //合并链表 t.next = next; if(next != null) next.prev = t; head.prev = t; //这一步确保了head.prev始终指向合并链表后的最后一个节点,没有这一步会遗漏掉节点, 并且只能指向t而不能是next } cur = next; } return head; } }