seo网站优化价格,实验室网站开发框架,如何选择免费网站建设,wordpress主体下载#x1f493; 博客主页#xff1a;C-SDN花园GGbond ⏩ 文章专栏#xff1a;数据结构经典题目刨析(c语言) 目录
一、题目描述
二、思路分析
三、代码实现 一、题目描述 二、思路分析
要完成一个带随机指针的链表的复制#xff0c;有一个巧妙的办法:分三步走 1.完成节… 博客主页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* pcurhead;while(pcur){Node*copy(Node*)malloc(sizeof(Node));//创建拷贝节点copy-valpcur-val;//拷贝数据copy-nextpcur-next;//插入到pcur后面pcur-nextcopy;pcurcopy-next;//移动pcur指针}
}
2.原链表中节点的随机指针拷贝 1.pcur指针重新指向第一个节点重新遍历链表 进入循环 2.拷贝指针指向pcur的下一个节点 3.如果pcur指针指向节点的随机指针指向NULL拷贝节点的随机指针则相同 否则拷贝节点的随即指针指向pcur的随机指针的下一个节点 这一部分实现代码如下
pcurhead;//指针重置while(pcur)//链表随机指针拷贝{Node*copypcur-next;if(pcur-randomNULL)copy-randomNULL;//对指向NULL的情况额外处理else{copy-randompcur-random-next;//随机指针拷贝的关键}pcurcopy-next;}
3.原链表中节点的next指针拷贝拷贝节点成为单独的新链表 1.pcur指针重新指向链表第一个节点 2.创建新链表的头指针和尾指针初始都指向空 3.进入循环——拷贝指针指向pcur的下一个节点 next指针指向拷贝指针的下一个节点 接下来将拷贝节点尾插到新链表并恢复原链表 如果新链表为空则新链表首尾指针都指向拷贝节点 否则新链表尾指针的next指向拷贝节点然后尾指针指向拷贝节点 再将pcur指针指向节点的next指向next指针对应的节点 循环直到pcur走向NULL 这一部分的实现代码如下并恢复的代码 pcurhead;Node*newheadNULL,*newtailNULL;while(pcur){Node*copypcur-next;//指向要拷贝的节点Node*nextcopy-next;//指向原链表原本的下一个节点if(newheadNULL)//将拷贝节点尾插到新链表上{newheadnewtailcopy;}else{newtail-nextcopy;newtailcopy;}pcur-nextnext;//恢复原链表pcurnext;}return newhead;
不恢复的代码
pcurhead-next;struct Node*newheadNULL;struct Node*newtailNULL;newheadnewtailhead-next;while(pcur-next){pcurpcur-next-next;newtail-nextpcur;newtailpcur;}newtail-nextNULL;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* pcurhead;while(pcur)//链表数据拷贝{Node*copy(Node*)malloc(sizeof(Node));//创建拷贝节点copy-valpcur-val;//拷贝数据copy-nextpcur-next;//插入到pcur后面pcur-nextcopy;pcurcopy-next;//移动pcur指针}pcurhead;//指针重置while(pcur)//链表随机指针拷贝{Node*copypcur-next;if(pcur-randomNULL)copy-randomNULL;//对指向NULL的情况额外处理else{copy-randompcur-random-next;//随机指针拷贝的关键}pcurcopy-next;}pcurhead;Node*newheadNULL,*newtailNULL;while(pcur){Node*copypcur-next;//指向要拷贝的节点Node*nextcopy-next;//指向原链表原本的下一个节点if(newheadNULL)//将拷贝节点尾插到新链表上{newheadnewtailcopy;}else{newtail-nextcopy;newtailcopy;}pcur-nextnext;//恢复原链表pcurnext;}return newhead;
}
