芯港小镇建设管理中心网站,如何进行网络营销服务创新,峡山网站建设,网店美工岗位要求你会得到一个双链表#xff0c;其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表#xff0c;也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表#xff0c;以此类推#xff0c;以生成如下面的示例…你会得到一个双链表其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表以此类推以生成如下面的示例所示的 多层数据结构 。
给定链表的头节点 head 将链表 扁平化 以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。
返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。
示例 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] 解释输入的多级列表如上图所示。 扁平化后的链表如下图 示例 3 输入head [] 输出[] 说明输入中可能存在空列表。 提示 节点数目不超过 1000 1 Node.val 105 如何表示测试用例中的多级链表
以 示例 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] 来源力扣LeetCode 链接https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list
方法一DFS
C提交内容
class Solution {
public:Node* flatten(Node* head) {functionNode*(Node*) dfs [](Node* node) {Node* cur node;Node* last nullptr;while (cur) {Node* next cur-next;if (cur-child) {Node* child_last dfs(cur-child);next cur-next;cur-next cur-child;cur-child-prev cur;if (next) {child_last-next next;next-prev child_last;}cur-child nullptr;last child_last;}else {last cur;}cur next;}return last;};dfs(head);return head;}
};
