中文题目
多级双向链表中,除了指向下一个节点和前一个节点指针之外,它还有一个子链表指针,可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示。
给定位于列表第一级的头节点,请扁平化列表,即将这样的多级双向链表展平成普通的双向链表,使所有结点出现在单级双链表中。
示例 1:
输入:head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] 输出:[1,2,3,7,8,11,12,9,10,4,5,6] 解释: 输入的多级列表如下图所示: 扁平化后的链表如下图:
示例 2:
输入:head = [1,2,null,3] 输出:[1,3,2] 解释: 输入的多级列表如下图所示: 1---2---NULL | 3---NULL
示例 3:
输入:head = [] 输出:[]
如何表示测试用例中的多级链表?
以 示例 1 为例:
1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULL
序列化其中的每一级之后:
[1,2,3,4,5,6,null] [7,8,9,10,null] [11,12,null]
为了将每一级都序列化到一起,我们需要每一级中添加值为 null 的元素,以表示没有节点连接到上一级的上级节点。
[1,2,3,4,5,6,null] [null,null,7,8,9,10,null] [null,11,12,null]
合并所有序列化结果,并去除末尾的 null 。
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
提示:
- 节点数目不超过
1000
1 <= Node.val <= 10^5
注意:本题与主站 430 题相同: https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/
通过代码
高赞题解
思路和心得:
1.递归和迭代两种都要掌握。经常问,经常用,经常考
(一)dfs
"""
# 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 flatten(self, head: 'Node') -> 'Node':
if head == None:
return head
dummy = Node(-1, None, None, None)
def dfs(pre: 'Node', cur: 'Node') -> 'Node':
if cur == None:
return pre
pre.next = cur
cur.prev = pre
nxt_head = cur.next #相当于4
tail = dfs(cur, cur.child) #相当于dfs(3, 7)
cur.child = None
return dfs(tail, nxt_head) #相当于dfs(12, 4)
dfs(dummy, head)
dummy.next.prev = None
return dummy.next
/*
// Definition for a Node.
class Node {
public:
int val;
Node* prev;
Node* next;
Node* child;
};
*/
class Solution
{
public:
Node * dummy;
Node* flatten(Node* head)
{
if (head == NULL)
return head;
this->dummy = new Node(-1, NULL, NULL, NULL);
dfs(dummy, head);
dummy->next->prev = NULL;
return dummy->next;
}
Node * dfs(Node * pre, Node * cur)
{
if (cur == NULL)
return pre;
pre->next = cur;
cur->prev = pre;
Node * next_head = cur->next;
Node * tail = dfs(cur, cur->child);
cur->child = NULL;
return dfs(tail, next_head);
}
};
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
};
*/
class Solution
{
Node dummy;
public Node flatten(Node head)
{
if (head == null)
return head;
this.dummy = new Node(-1, null, null, null);
dfs(dummy, head);
dummy.next.prev = null;
return dummy.next;
}
public Node dfs (Node pre, Node cur)
{
if (cur == null)
return pre;
pre.next = cur;
cur.prev = pre;
Node next_head = cur.next;
Node tail = dfs(cur, cur.child);
cur.child = null;
return dfs(tail, next_head);
}
}
(二)栈迭代
"""
# 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 flatten(self, head: 'Node') -> 'Node':
if head == None:
return head
dummy = Node(-1, None, None, None)
pre = dummy
stk = [head]
while stk:
x = stk.pop()
pre.next = x
x.prev = pre
if x.next:
stk.append(x.next)
if x.child:
stk.append(x.child)
x.child = None
pre = x
dummy.next.prev = None
return dummy.next
/*
// Definition for a Node.
class Node {
public:
int val;
Node* prev;
Node* next;
Node* child;
};
*/
class Solution
{
public:
Node* flatten(Node* head)
{
if (head == NULL)
return head;
Node * dummy = new Node(-1, NULL, NULL, NULL);
Node * pre = dummy;
stack<Node *> stk;
stk.push(head);
while (!stk.empty())
{
Node * x = stk.top(); stk.pop();
pre->next = x;
x->prev = pre;
if (x->next)
stk.push(x->next);
if (x->child)
{
stk.push(x->child);
x->child = NULL;
}
pre = x;
}
dummy->next->prev = NULL;
return dummy->next;
}
};
/*
// 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)
{
if (head == null)
return head;
Node dummy = new Node(-1, null, null, null);
Node pre = dummy;
Deque<Node> stk = new LinkedList<>();
stk.push(head);
while (!stk.isEmpty())
{
Node x = stk.poll();
pre.next = x;
x.prev = pre;
if (x.next != null)
stk.push(x.next);
if (x.child != null)
{
stk.push(x.child);
x.child = null;
}
pre = x;
}
dummy.next.prev = null;
return dummy.next;
}
}
统计信息
通过次数 | 提交次数 | AC比率 |
---|---|---|
3656 | 5801 | 63.0% |
提交历史
提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
---|