题目

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

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

示例 1：

思路

转换题目，可以将题作为双向链表插入多段链表来做 遍历链表，遇到子链表将其插入到父链表中

代码

/*
// 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;
        fun(head);
        return head;
    }

    public void fun(Node head){
          
   
        Node cur = head;
        while(cur != null){
          
   
            if(cur.child != null){
          
   
                Node tmp = cur.next;
                cur.next = cur.child;
                cur.next.prev = cur;
                cur.child = null;
                //找子链表的结尾
                Node last = cur;
                while(last.next != null){
          
   
                    last = last.next;
                }
                last.next = tmp;
                if(tmp != null){
          
   
                    tmp.prev = last;
                }
            }
            cur = cur.next;
        }
    }
}