430. Flatten a Multilevel Doubly Linked List #

题目 #

给定一个双链表，各节点有一个 next 指针、一个 prev 指针和一个的 child 指针 。这个 child 指针 可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，从而构成 多层数据结构 。

给定链表的头节点 head ，将链表 扁平化 ，使所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后和 curr.next 之前。

返回 扁平列表的 head 。列表中的节点必须将其所有子指针设置为 null 。

思路 #

代码 #

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    public Node getTail(Node head) {
        if (head.child == null && head.next == null) return head;
        else if (head.child != null && head.next != null) {
            Node tail = getTail(head.child);
            
            tail.next = head.next;
            head.next.prev = tail;
            
            head.next = head.child;
            head.child.prev = head;
            
            head.child = null;
            
            return getTail(head.next.next);
        }
        else if (head.child != null && head.next == null) {
            head.next = head.child;
            head.child.prev = head;
            head.child = null;
            return getTail(head.next);
        }
        else return getTail(head.next);
    }
    public Node flatten(Node head) {
        if (head == null) return null;
        getTail(head);
        return head;
    }
}