430-扁平化多级双向链表（Flatten a Multilevel Doubly Linked List）

题目描述
中文描述：
您将获得一个双向链表，除了下一个和前一个指针之外，它还有一个子指针，可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

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

英文描述：
You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

示例

示例说明：
给出以下多级双向链表：

应该返回如下所示的扁平双向链表:

好的，题目描述到此结束，接下来分析问题。
问题本身并不难以理解，就是将一个多级链表转化为一个单级链表，这里我们利用暴力思想：首先给定头结点

1. 如果当前结点是一个普通结点（结点不为空，结点的下一个不为空并且该结点无子链），我们就让这个结点指向这个结点的下一个结点。

if(temp != null && temp.child == null && temp.next != null){       //普通节点
                temp = temp.next;
            }

2. 如果当前结点不为空且有子链，我们就对其进行操作。具体操作如下：
   • 首先，我们让子链的头结点的前驱（prev）指向我们当前的结点
   • 然后，我们让当前结点的子链指向null
   • 如果当前结点有下一个结点（next），则将其压栈
   • 令当前结点指向子链的头结点

else if(temp != null && temp.child != null){                             //有子节点
                Node cur = temp.child;
                temp.child = null;
                cur.prev = temp;
                if(temp.next != null){                                          //如果有下一个结点，则将其压栈
                     stack.push(temp.next);
                }
                temp.next = cur;
                temp = temp.next;                                               //更换子节点的头结点的prev后进行
            }

3. 如果当前结点是子链的最后一个结点，我们就弹栈，并让当前结点指向弹出的结点。

 else if(temp.next == null && !stack.isEmpty()){                          //子节点的最后一个节点
                Node cur = stack.pop();
                temp.next = cur;
                cur.prev = temp;
                temp = temp.next;
            }

4. 如果当前结点是主链的最后一个结点，则结束循环，输出结果。

else if(temp.next == null && stack.isEmpty()){
                temp.next = null;
                break;
            }

现在让我们看一下完整版代码

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
    public Node flatten(Node head) {
        if(head == null)
            return head;
        if(head.next == null && head.child == null)
            return head;
        Node temp = head;
        Node res = temp;
        Stack<Node> stack = new Stack<Node>();
        while(true){
            if(temp != null && temp.child == null && temp.next != null){       //普通节点
                temp = temp.next;
            }
            else if(temp != null && temp.child != null){                             //有子节点
                Node cur = temp.child;
                temp.child = null;
                cur.prev = temp;
                if(temp.next != null){                                          //如果有下一个结点，则将其压栈
                     stack.push(temp.next);
                }
                temp.next = cur;
                temp = temp.next;                                               //更换子节点的头结点的prev后进行
            }
            else if(temp.next == null && !stack.isEmpty()){                          //子节点的最后一个节点
                Node cur = stack.pop();
                temp.next = cur;
                cur.prev = temp;
                temp = temp.next;
            }
            else if(temp.next == null && stack.isEmpty()){
                temp.next = null;
                break;
            }
        }
        return res;
    }
}

这道题目并不困难，只是其中的细节要注意，比如在连接到子链的时候注意要修改子链的prev和当前结点的child结点即可。
题目中使用到了栈，大家也可以尝试使用递归来试试本题。