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

本文主要是介绍430. Flatten a Multilevel Doubly Linked List | 430. 扁平化多级双向链表（DFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

题解

思路不难，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;}
}

这篇关于430. Flatten a Multilevel Doubly Linked List | 430. 扁平化多级双向链表（DFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---