扁平化多级双向链表 leetcode

Question

给你一个双向链表，除了 next 和 previous 指针外，它还可以有一个子指针，它可能指向也可能不指向一个单独的双向链表。这些子列表可能有自己的一个或多个子列表，依此类推，以产生多级数据结构，如下例所示。

展平列表，使所有节点出现在单级双向链表中。您将获得列表第一级的头部。

class Solution {
/*Global variable pre to track the last node we visited */
    Node pre = null;
    public Node flatten(Node head) {
        if (head == null) {
            return null; 
        }
/*Connect last visted node with current node */
        if (pre != null) {
            pre.next = head; 
            head.prev = pre;
        }

        pre = head; 
/*Store head.next in a next pointer in case recursive call to flatten head.child overrides head.next*/
        Node next = head.next; 

        flatten(head.child);
        head.child = null;

        flatten(next);        
        return head; 
    }
}

对于题目，上面的leetcode解法有效。但是我不明白这个：

/*Store head.next in a next pointer in case recursive call to flatten head.child overrides head.next*/
        Node next = head.next;

谁能解释一下这部分？ head.child 如何覆盖 head.next？

Answer 1

flatten(head.child) 可能会改变 head.next 由于我们将上次访问的节点与当前节点连接的部分：

if (pre != null) {
  pre.next = head; 
  head.prev = pre;
}

在这个阶段，pre 代表更老的 head，head 代表 head.child。所以我们实际上将 head 与其 child 连接起来。但是如果我们这样做，我们将失去与实际 head.next 的联系，因此我们必须将它保存在一个名为 next 的额外变量中。这就是我们在调用 flatten() 函数之前保留它的原因。

扁平化多级双向链表 leetcode

Flatten a Multilevel Doubly Linked List leetcode

java

linked-list

data-structures