🌕 430. 扁平化多级双向链表

难度: 🌕

问题描述

---

解法

/*
// 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) {
        // 思路：
        // 递归
        Node[] res = mySol(head);
        return res[0];
    }

    private Node[] mySol(Node head) {
        Node[] res = new Node[2];
        
        Node cur = head;
        Node p = null;
        while(cur != null) {
            // System.out.println(cur.val);
            if(cur.child != null) {
                Node next =cur.next;

                Node[] c = mySol(cur.child);  
                cur.child = null;             
                cur.next = c[0];
                c[0].prev = cur;
                c[1].next = next;
                if(next != null) {
                    next.prev = c[1];
                }
                cur = next;
                p = c[1];
            } else {
                p = cur;
                cur = cur.next;
            }
        }
        res[0] = head;
        res[1] = p;
        return res;
    }
}

---

输出