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

一时失言乱红尘 2022-09-03 15:20 42阅读 0赞

## 题目 ##

[https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/][https_leetcode.com_problems_flatten-a-multilevel-doubly-linked-list]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

思路不难，DFS。

指针操作比较坑，注意边界以及特殊情况，所以多定义了几个变量用来“接着”过程中的值。

/* // 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) { 
            dfs(head);
            return head;
        }
    
        public Node dfs(Node node) { 
            Node pre = node;
            if (node == null) return null;
            
            while (node != null) { 
                if (node.child == null) { 
                    node = node.next;
                } else { 
                    Node next = node.next;
    
                    Node nextEnd = dfs(node.child); // 我们认为后面的已经用递归flatten完成
                    nextEnd.next = next;
                    if (next != null) next.prev = nextEnd;
    
                    node.next = node.child;
                    node.child.prev = node;
    
                    node.child = null;
                    node = next;
                }
            }
    
            while (pre.next != null) {  // 返回(flatten后的)下一行最后一个元素
                pre = pre.next;
            }
            return pre;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_flatten-a-multilevel-doubly-linked-list]: https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/fdc5c1e2a04a4921bda2fd1b37319020.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/86536846d19a49cf964b459ec39e3fbb.png