首页 > 代码库 > Copy List with Random Pointer
Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
参考：深度拷贝，浅度拷贝，Lazy拷贝解析http://www.2cto.com/kf/201401/276086.html
思路： Step 1: 首先指向在原链表的每个节点后面，复制一个新的节点，原链表长度变为 2 倍
random 指针指向的是 原链表节点 random 指针指向的节点的后面的那个节点
Step 2: 将链表拆成两个 lists
C++实现代码：
#include<iostream>#include<new>using namespace std;// Definition for singly-linked list with a random pointer.struct RandomListNode{ int label; RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) {}};class Solution{public: RandomListNode *copyRandomList(RandomListNode *head) { if(head==NULL) return NULL; RandomListNode *p=head; while(p) { RandomListNode *q=new RandomListNode(p->label); q->next=p->next; p->next=q; p=q->next; } p=head; while(p) { if(p->random) p->next->random=p->random->next; p=p->next->next; } RandomListNode *retHead = NULL; RandomListNode *tRet = NULL; p = head; while(p) { if(retHead == NULL) { retHead = p->next; tRet = retHead; p->next = p->next->next; p = p->next; } else { tRet->next = p->next; p->next = p->next->next; p = p->next; tRet = tRet->next; } } return retHead; } void createList(RandomListNode *&head) { RandomListNode *p=NULL; int i=0; int arr[10]= {10,9,8,7,6,5,4,3,2,1}; for(i=0; i<10; i++) { if(head==NULL) { head=new RandomListNode(arr[i]); if(head==NULL) return; } else { p=new RandomListNode(arr[i]); p->next=head; head=p; } } }};int main(){ Solution s; RandomListNode *L=NULL; s.createList(L); RandomListNode *L2=s.copyRandomList(L); RandomListNode *p=L2; while(p) { cout<<p->label<<" "; p=p->next; }}
Copy List with Random Pointer
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。