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

怼烎@ 2022-01-26 02:07 243阅读 0赞

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

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

英文描述：  
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.

**示例**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpMTM3NjQxNzUzOQ_size_16_color_FFFFFF_t_70]  
**示例说明：  
给出以下多级双向链表：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpMTM3NjQxNzUzOQ_size_16_color_FFFFFF_t_70 1]  
**应该返回如下所示的扁平双向链表:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpMTM3NjQxNzUzOQ_size_16_color_FFFFFF_t_70 2]  
好的，题目描述到此结束，接下来分析问题。  
问题本身并不难以理解，就是将一个多级链表转化为一个单级链表，这里我们利用暴力思想：首先给定头结点

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

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

1.  如果当前结点不为空且有子链，我们就对其进行操作。具体操作如下：
    
     *  **首先，我们让子链的头结点的前驱（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后进行
                }

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

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

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

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结点即可**。  
题目中使用到了栈，大家也可以尝试使用**递归**来试试本题。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpMTM3NjQxNzUzOQ_size_16_color_FFFFFF_t_70]: /images/20220126/12c19e89bf8e42f5b4dd5eb015d85e2a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpMTM3NjQxNzUzOQ_size_16_color_FFFFFF_t_70 1]: /images/20220126/b468e9e40f324dfc96b612af1e235b79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpMTM3NjQxNzUzOQ_size_16_color_FFFFFF_t_70 2]: /images/20220126/88c6a6be125a42fb94a56fe405f96c3a.png