[leetcode] 430. Flatten a Multilevel Doubly Linked List

[leetcode] 430. Flatten a Multilevel Doubly Linked List

Description

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.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]Output: [1,2,3,7,8,11,12,9,10,4,5,6]Explanation:The multilevel linked list in the input is as follows:

After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3]Output: [1,3,2]Explanation:The input multilevel linked list is as follows: 1---2---NULL | 3---NULL

Example 3:

Input: head = []Output: []

How multilevel linked list is represented in test case:

We use the multilevel linked list from Example 1 above:

1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULL

The serialization of each level is as follows:

[1,2,3,4,5,6,null][7,8,9,10,null][11,12,null]To serialize all levels together we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:[1,2,3,4,5,6,null][null,null,7,8,9,10,null][null,11,12,null]

Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

Constraints:

The number of Nodes will not exceed 1000.1 <= Node.val <= 105

分析

题目的意思是：给定双向链表，把双向链表的孩子节点拼接成一条拼接在当前节点的后面，然后构成一条链，类似于一个flatten的操作。我这里参考了一下别人的思路，用递归。

定义递归函数 dfs(prev, cur)，它接收两个指针作为函数参数并返回扁平化列表中的尾部指针。cur 指针指向要扁平化的子列表，prev 指针指向 cur 指向元素的前一个元素。在函数 dfs(prev, cur)，首先在 prev 和 curr 节点之间建立双向连接然后在函数中调用 dfs(cur, curr.child) 对左子树（curr.child 即子列表）进行操作，它将返回扁平化子列表的尾部元素 tail，再调用dfs(tail, curr.next) 对右子树进行操作在调用 dfs(cur, cur.child) 之前，应该复制 cur.next 指针，因为 cur.next 可能在函数中改变在扁平化 cur.child 指针所指向的列表以后，应该删除 child 指针，因为最终不再需要该指针

代码

"""# Definition for a Node.class Node: def __init__(self, val, prev, next, child): self.val = val self.prev = prev self.next = next self.child = child"""class Solution: def dfs(self,prev,cur): if(not cur): return prev cur.prev=prev prev.next=cur t=cur.next tail=self.dfs(cur,cur.child) cur.child=None return self.dfs(tail,t) def flatten(self, head: 'Node') -> 'Node': if(not head): return None prev=Node(None,None,head,None) self.dfs(prev,head) prev.next.prev=None return prev.next

参考文献

​​扁平化多级双向链表​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。