一、问题描述
习题摘自
二、解题思路
要完成一个带随机指针的链表的复制，有一个巧妙的办法:
分三步走
- 完成节点数据拷贝——在原链表的每个节点后面增加一个拷贝节点，拷贝节点的值等于原节点的值
- 完成节点的随机指针拷贝——原节点的随机指针指向哪里，拷贝节点就指向对应节点的下一个节点（这一部分是这条思路能实现的关键）
- 完成节点的next指针拷贝——将拷贝节点从原链表中取下，按顺序改变next指针指向，组成新的链表，并恢复原链表的next指针
三、代码实现
代码的实现逻辑:
需要用到三个循环
假设初始链表如下
1. 原链表中节点的数据拷贝
第一个循环：
- 创建pcur指针指向链表第一个节点，遍历链表
- 在每个节点后面创建一个相同结构的拷贝节点，拷贝原节点数据
- 修改链表next指针指向如下：
- 原链表节点-＞该节点拷贝节点-＞原链表下一个节点-＞该节点拷贝节点……原链表最后一个节点-＞该节点拷贝节点-＞NULL
经过第一轮循环后，原链表每个节点之后被插入了一个新节点
这一部分的实现代码如下
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ typedef struct Node Node; struct Node* copyRandomList(struct Node* head) { Node* pcur=head; while(pcur) { Node*copy=(Node*)malloc(sizeof(Node));//创建拷贝节点 copy->val=pcur->val;//拷贝数据 copy->next=pcur->next;//插入到pcur后面 pcur->next=copy; pcur=copy->next;//移动pcur指针 } }
2.原链表中节点的随机指针拷贝
注意：
随机指针不是单纯的拷贝，而是将拷贝节点的随机指针指向与原链表中关系对应的拷贝节点
第二个循环:
- pcur指针重新指向第一个节点，重新遍历链表
- 进入循环
- 拷贝指针指向pcur的下一个节点
- 如果pcur指针指向节点的随机指针指向NULL，拷贝节点的随机指针则相同
- 否则拷贝节点每次指向pcur指针指向节点的下一个节点
- 修改拷贝节点的随机指针，令其指向pcur指针指向节点的随机指针指向的节点的下一个节点
- 然后pcur指针指向拷贝节点的下一个节点，拷贝指针指向pcur指针的下一个节点
这一部分实现代码如下
pcur=head;//指针重置 while(pcur)//链表随机指针拷贝 { Node*copy=pcur->next; if(pcur->random==NULL) copy->random=NULL;//对指向NULL的情况额外处理 else { copy->random=pcur->random->next;//随机指针拷贝的关键 } pcur=copy->next; }
3.原链表中节点的next指针拷贝，拷贝节点成为单独的新链表
第三个循环:
- pcur指针重新指向链表第一个节点
- 创建新链表的头指针和尾指针初始都指向空
- 进入循环——拷贝指针指向pcur的下一个节点
- next指针指向拷贝指针的下一个节点
- 接下来将拷贝节点尾插到新链表，并恢复原链表
- 如果新链表为空，则新链表首尾指针都指向拷贝节点
- 否则，新链表尾指针的next指向拷贝节点，然后尾指针指向拷贝节点
- 再将pcur指针指向节点的next指向next指针对应的节点
- 循环直到pcur走向NULL
这一部分的实现代码如下
别忘记拷贝完成之后，返回新链表的地址
pcur=head; Node*newhead=NULL,*newtail=NULL; while(pcur) { Node*copy=pcur->next;//指向要拷贝的节点 Node*next=copy->next;//指向原链表原本的下一个节点 if(newhead==NULL)//将拷贝节点尾插到新链表上 { newhead=newtail=copy; } else { newtail->next=copy; newtail=copy; } pcur->next=next;//恢复原链表 pcur=next; } return newhead;
完整代码
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ typedef struct Node Node; struct Node* copyRandomList(struct Node* head) { Node* pcur=head; while(pcur)//链表数据拷贝 { Node*copy=(Node*)malloc(sizeof(Node));//创建拷贝节点 copy->val=pcur->val;//拷贝数据 copy->next=pcur->next;//插入到pcur后面 pcur->next=copy; pcur=copy->next;//移动pcur指针 } pcur=head;//指针重置 while(pcur)//链表随机指针拷贝 { Node*copy=pcur->next; if(pcur->random==NULL) copy->random=NULL;//对指向NULL的情况额外处理 else { copy->random=pcur->random->next;//随机指针拷贝的关键 } pcur=copy->next; } pcur=head; Node*newhead=NULL,*newtail=NULL; while(pcur) { Node*copy=pcur->next;//指向要拷贝的节点 Node*next=copy->next;//指向原链表原本的下一个节点 if(newhead==NULL)//将拷贝节点尾插到新链表上 { newhead=newtail=copy; } else { newtail->next=copy; newtail=copy; } pcur->next=next;//恢复原链表 pcur=next; } return newhead; }
