430. Flatten a Multilevel Doubly Linked List(扁平化多级双向链表)
题目描述
您将获得一个双向链表,除了下一个和前一个指针之外,它还有一个子指针,可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示。
扁平化列表,使所有结点出现在单级双链表中。您将获得列表第一级的头部。
示例:
输入:
1—2---3—4---5—6–NULL
|
7—8---9—10–NULL
|
11–12–NULL
输出:
1-2-3-7-8-11-12-9-10-4-5-6-NULL
以上示例的说明:
给出以下多级双向链表:
我们应该返回如下所示的扁平双向链表:
方法思路
Approach1:
Basic idea is straight forward:
1.Start form the head , move one step each time to the next node
2.When meet with a node with child, say node p, follow its child chain to the end and connect the tail node with p.next, by doing this we merged the child chain back to the main thread。
3.Return to p and proceed until find next node with child.
4.Repeat until reach null
class Solution {
//Runtime: 1 ms, faster than 100.00%
//Memory Usage: 37.5 MB, less than 26.05%
public Node flatten(Node head) {
if( head == null) return head;
// Pointer
Node p = head;
while( p!= null) {
// CASE 1: if no child, proceed
if( p.child == null ) {
p = p.next;
continue;
//continue 适用于任何循环控制结构中。作用是让程序立刻跳转到下一次循环的迭代
//在 for 循环中,continue 语句使程序立即跳转到更新语句
//在 while 或者 do…while 循环中,程序立即跳转到布尔表达式的判断语句
}
// CASE 2: got child, find the tail of the child and link it to p.next
Node temp = p.child;
// Find the tail of the child
while( temp.next != null )
temp = temp.next;
// Connect tail with p.next, if it is not null
temp.next = p.next;
if( p.next != null ) p.next.prev = temp;
// Connect p with p.child, and remove p.child
p.next = p.child;
p.child.prev = p;
p.child = null;
}
return head;
}
}
Approach2: recursive
第一种递归方法:
class Solution{
//Runtime: 1 ms, faster than 100.00%
//Memory Usage: 36.4 MB, less than 85.29%
Node pre = null;
public Node flatten(Node head) {
flattenHelper(head);
return head;
}
public void flattenHelper (Node head){
if(head == null) return;
Node post = head.next;
Node child = head.child;
if(pre != null){
pre.next = head;
head.prev = pre;
pre.child = null;
}
pre = head;
flattenHelper(child);
flattenHelper(post);
}
}
第二种递归方法:
class Solution{
public Node flatten(Node head) {
flattentail(head);
return head;
}
// flattentail: flatten the node "head" and return the tail in its child (if exists)
// the tail means the last node after flattening "head"
// Five situations:
// 1. null - no need to flatten, just return it
// 2. no child, no next - no need to flatten, it is the last element, just return it
// 3. no child, next - no need to flatten, go next
// 4. child, no next - flatten the child and done
// 5. child, next - flatten the child, connect it with the next, go next
//Runtime: 1 ms, faster than 100.00%
//Memory Usage: 36.5 MB, less than 82.35%
private Node flattentail(Node head) {
if (head == null) return head; // CASE 1
if (head.child == null) {
if (head.next == null) return head; // CASE 2
return flattentail(head.next); // CASE 3
}
else {
Node child = head.child;
head.child = null;
Node next = head.next;
Node childtail = flattentail(child);
head.next = child;
child.prev = head;
if (next != null) { // CASE 5
childtail.next = next;
next.prev = childtail;
return flattentail(next);
}
return childtail; // CASE 4
}
}
}
上一篇: EJ.03 用私有构造器或者枚举类型强化Singleton属性
下一篇: leetcode 430. flatten-a-multilevel-doubly-linked-list扁平化多级双向链表 python3
推荐阅读
-
430. Flatten a Multilevel Doubly Linked List
-
LeetCode解题分享:430. Flatten a Multilevel Doubly Linked List
-
【LeetCode】430. Flatten a Multilevel Doubly Linked List 解题报告(Python)
-
430. Flatten a Multilevel Doubly Linked List
-
[LC] 430. Flatten a Multilevel Doubly Linked List
-
430-扁平化多级双向链表(Flatten a Multilevel Doubly Linked List)
-
LeetCode 430. Flatten a Multilevel Doubly Linked List
-
[LeetCode] 430. Flatten a Multilevel Doubly Linked List
-
430. Flatten a Multilevel Doubly Linked List(扁平化多级双向链表)
-
leetcode 430. flatten-a-multilevel-doubly-linked-list扁平化多级双向链表 python3