剑指offer35.复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

完整代码

刚开始看题时还有点摸不着头脑，感觉这道题没有任何存在的意义。后来看了大家的讨论才明白。 思想：复制后的链表不能利用原来链表的空间，需要申请一块新的空间，即使是NULL，也要从新赋一个新的NULL

/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { //题目的关键在于使用一块新的存储空间，而不是在原有空间上做文章 if(pHead==NULL) return NULL; RandomListNode* p,*n,*c,*new_head; //p是当前节点，n是当前节点的下一个节点，c是复制的节点 //首先将原节点复制插入到该节点的后面 p=pHead; while(p){ n=p->next;//记住当前节点的下一个节点的位置 c=new RandomListNode(p->label);//复制当前节点的值 //将该节点链接在p节点的后面 p->next=c; c->next=n; p=n;//p后移 } //修改赋值的节点的随机指针域 p=pHead; while(p){ c=p->next;//复制节点是当前节点的下一个节点 if(p->random) c->random=p->random->next;//复制节点的随机指针也是当前节点的随机指针的下一个节点 else c->random=NULL; p=c->next;//后移 } //将复制后的节点和原节点分开 p=pHead; new_head=p->next; c=new_head; while(p){ //拆分 n=c->next; p->next=n; if(n) c->next=n->next; else c->next=NULL; //更新 p=n; if(p)//这一点很重要，当p为空时，p的next就没有意义，会导致程序不通过 c=p->next; } return new_head; } };

使用map来实现，将复制节点和原节点绑定

/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { //题目的关键在于使用一块新的存储空间，而不是在原有空间上做文章 if(pHead==NULL) return NULL; //使用哈希表来实现，哈希表中将复制节点和原节点绑在一起 map<RandomListNode*,RandomListNode*> m; RandomListNode* p,*nhead,*c,*t; //nhead指向复制的节点的头节点 //p、c分别指向原链表正在操作的最后一个节点 //t用来新创建一个复制节点 //先处理头节点 p=pHead; nhead=new RandomListNode(p->label); c=nhead; m[pHead]=nhead; p=p->next; //先复制节点，同时将random指针存放到map中 while(p){ t=new RandomListNode(p->label); c->next=t; c=t; m[p]=t; p=p->next; } //将复制链表每一个节点的random指针，指向相应的节点 p=pHead; c=nhead; while(p){ c->random=m[p->random];//这一步很关键，将当前复制节点的random指向原节点的random指向的节点 p=p->next; c=c->next; } return nhead; } };

二刷 掌握了基本思想，但是在小细节上容易出错，出错点在：

程序中出现了访问空指针的next域或者random域。将复制完的链表断开后，未将原链表连接上。 /* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(pHead == NULL) return NULL; //1.先将链表中的每一个节点next域进行复制 RandomListNode* p = pHead; while(p){ RandomListNode *cur = new RandomListNode(p->label); cur->next = p->next; p->next = cur; p = cur->next; } //2.复制节点的random域 p = pHead; while(p){ RandomListNode *c_p = p->next; if(p->random)//判断的目的是避免出现p->random域为空时，访问p->random->next c_p->random = p->random->next; p = c_p->next; } //3.将复制的链表进行断开 p = pHead; RandomListNode *c_p = p->next; while(p){ RandomListNode* cur = p->next; p->next = cur->next; p = cur->next; if(p)//判断的目的是避免出现：当p为空时，访问p->next,这样会出现段错误 cur->next = p->next; } return c_p; } };