leetcode如何实现复制带随机指针的链表
小编给大家分享一下leetcode如何实现复制带随机指针的链表,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
我们提供的服务有:成都网站建设、成都做网站、微信公众号开发、网站优化、网站认证、谢通门ssl等。为超过千家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的谢通门网站制作公司
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
示例:
输入:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
解释:
节点 1 的值是 1,它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2,它的下一个指针指向 null,随机指针指向它自己。
提示:
你必须返回给定头的拷贝作为对克隆列表的引用。
解题技巧:
1,因为random指针的存在,所以copy的时候如何定位random是个问题,所以简单方法在原链表每个位置后面插入一个元素。
2,由于random可能指向前面的指针,所以复制完之前不能拆解
3,注意边界条件,对于指针类题目,一定要判断空情况
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node() {}
Node(int _val, Node* _next, Node* _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
Node* h=NULL;
Node* t=NULL;
Node* cur=NULL;
cur=head;
while(cur!=NULL){
t=cur->next;
cur->next=new Node(cur->val,t,NULL);
cur=t;
}
cur=head;
if (cur==NULL){
return NULL;
}
h=cur->next;
t=h;
while(cur!=NULL){
if (cur->random!=NULL){
t->random=cur->random->next;
}
cur=t->next;
if (cur!=NULL){
t=cur->next;
}
}
cur=head;
h=cur->next;
t=h;
while(cur!=NULL){
cur->next=t->next;
cur=cur->next;
if (cur!=NULL){
t->next=cur->next;
t=t->next;
}
}
return h;
}
};
以上是“leetcode如何实现复制带随机指针的链表”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!
文章题目:leetcode如何实现复制带随机指针的链表
文章出自:http://scyanting.com/article/jpjsso.html