0430. Flatten a Multilevel Doubly Linked List¶
题目信息¶
- 题号:
0430
- 难度:
Medium
- 主题:
多级双向链表、子链表、深度优先顺序、原地重连
- 原题:
- 重点:
子链表插入父节点与原后继之间、递归处理多层
child、保持prev/next一致、最终所有child为空
题目重述¶
给定一个多级双向链表的头节点 head。每个节点除 prev 和 next 外,还可能通过 child 指向另一条双向链表,该子链表还可以继续包含子链表。
把整个结构原地展平成一条普通双向链表:遇到带有 child 的节点时,先接入并完整展开其子链表,再继续原链表中该节点原来的后继。返回展平后的头节点。结果中所有节点必须恰好出现一次,prev 和 next 必须互相对应,所有 child 指针必须设为空。
节点总数位于 [0, 1000],节点值位于 [1, 10^5]。输入为空时返回 null。
自建示例¶
包含两层子链表:
输入:主链表 1 <-> 2 <-> 3;节点 2 的 child 为 4 <-> 5;节点 4 的 child 为 6
输出:1 <-> 2 <-> 4 <-> 6 <-> 5 <-> 3
解释:节点 2 的子链表插入 2 和 3 之间;进入节点 4 时先展开其子节点 6,再回到节点 5。最终所有 child 均为空。
空链表:
输入:head = null
输出:null
解释:没有节点需要展平。
展开子链表并返回它的尾节点¶
沿主链表扫描。遇到 child 时,先保存当前节点原来的 next,递归把子链表展平并得到子链表尾部,再把当前节点接到子链表头,把子链表尾接回原后继;最后清空 child。返回尾节点让外层能够一次完成回接,而不必重新扫描刚展开的子链表。
C++ 实现¶
class Solution {
Node* flattenTail(Node* head) {
Node* current = head;
Node* tail = head;
while (current != nullptr) {
Node* next = current->next;
if (current->child != nullptr) {
Node* child = current->child;
Node* childTail = flattenTail(child);
current->child = nullptr;
current->next = child;
child->prev = current;
if (next != nullptr) {
childTail->next = next;
next->prev = childTail;
}
tail = childTail;
} else {
tail = current;
}
current = next;
}
return tail;
}
public:
Node* flatten(Node* head) {
if (head == nullptr) return nullptr;
flattenTail(head);
return head;
}
};
代码分析¶
保存原后继保证子链表展开后仍能回到主链;每次接入都同时更新两个方向的指针并清空 child,不会丢失或重复节点。每个节点被处理一次,时间复杂度为 O(n),递归栈空间为 O(h)。