「复制带随机指针的链表」的一个很巧妙解法
16lz
2021-01-22
题目来源于 LeetCode 上第 138 号问题：复制带随机指针的链表。题目难度为 Medium，目前通过率为 40.5% 。
题目描述
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
题目解析
在原链表的每个节点后面拷贝出一个新的节点
依次给新的节点的随机指针赋值：cur->next->random = cur->random->next
断开链表可得到深度拷贝后的新链表
之所以说这个方法比较巧妙是因为相较于一般的解法（如使用 Hash map ）来处理，上面这个解法 不需要占用额外的空间。
动画描述
代码实现
我发现带指针的题目使用 C++ 版本更容易描述，所以下面的代码实现是 C++ 版本。
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if (!head) return NULL;
RandomListNode *cur = head;
while (cur) {
RandomListNode *node = new RandomListNode(cur->label);
node->next = cur->next;
cur->next = node;
cur = node->next;
}
cur = head;
while (cur) {
if (cur->random) {
cur->next->random = cur->random->next;
}
cur = cur->next->next;
}
cur = head;
RandomListNode *res = head->next;
while (cur) {
RandomListNode *tmp = cur->next;
cur->next = tmp->next;
if(tmp->next) tmp->next = tmp->next->next;
cur = cur->next;
}
return res;
}
};更多相关文章
- 使用快慢指针求解「环形链表」so easy！
- SSH AKS集群节点的几种方法（一）
- 动画：面试算法之求二叉树的下一节点
- php+nodeJs+thrift协议，实现zookeeper节点数据自动发现
- 2021.1.17——指针和结构体的初步认识
- jQuery的DOM操作实例（3）——创建节点&&编写一个弹窗
- jQuery编程基础精华02（属性、表单过滤器，元素的each，表单选择器，子元
- 如何在java脚本中获取节点内部文本?
- Study JQuery《zTree自动点击第一个节点》