当前位置：首页 > news >正文

【数据结构算法经典题目刨析（c语言）】随机链表的复制（图文详解）

news 来源：原创 2024/9/19 22:14:26

💓 博客主页：C-SDN花园GGbond

⏩ 文章专栏：数据结构经典题目刨析(c语言)

一、题目描述

二、思路分析

三、代码实现

一、题目描述

二、思路分析

要完成一个带随机指针的链表的复制，有一个巧妙的办法:分三步走

1.完成节点数据拷贝——在原链表的每个节点后面增加一个拷贝节点，拷贝节点的值等于原节点的值
2.完成节点的随机指针拷贝——原节点的随机指针指向哪里，拷贝节点就指向对应节点的下一个节点（这一部分是这条思路能实现的关键）
3.完成节点的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.原链表中节点的随机指针拷贝

1.pcur指针重新指向第一个节点，重新遍历链表
进入循环
2.拷贝指针指向pcur的下一个节点
3.如果pcur指针指向节点的随机指针指向NULL，拷贝节点的随机指针则相同
否则拷贝节点的随即指针指向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指针拷贝，拷贝节点成为单独的新链表

1.pcur指针重新指向链表第一个节点
2.创建新链表的头指针和尾指针初始都指向空
3.进入循环——拷贝指针指向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;

不恢复的代码

pcur=head->next;struct Node*newhead=NULL;struct Node*newtail=NULL;newhead=newtail=head->next;while(pcur->next){pcur=pcur->next->next;newtail->next=pcur;newtail=pcur;}newtail->next=NULL;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;
}