拷贝有随机指针的链表

[编程题]拷贝有随机指针的链表

热度指数：37249 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现在有一个这样的链表：链表的每一个节点都附加了一个随机指针，随机指针可能指向链表中的任意一个节点或者指向空。

请对这个链表进行深拷贝。

说明：本题目包含复杂数据结构ListNode、RandomListNode，点此查看相关信息

算法知识视频讲解

华科不平凡

发表于 2020-09-23 16:16:19

细胞分裂法：增殖：遍历next指针，拷贝旧节点，并将新节点插入到旧节点之后复制：遍历next指针，如果某个节点的random不为空（旧节点），则下一个节点（新节点）的random指向该节点random指向节点的下一个节点分裂：遍历next指针，将两个链表分裂开来代码如下： // // 展开全文

宫水三叶的刷题日记

发表于 2021-09-06 11:01:13

模拟 + 哈希表如果不考虑 random 指针的话，对一条链表进行拷贝，我们只需要使用两个指针：一个用于遍历原链表，一个用于构造新链表（始终指向新链表的尾部）即可。这一步操作可看做是「创建节点 + 构建 next 指针关系」。现在在此基础上增加一个 random 指针，我们可以将 next 指针展开全文