[ 链表OJ题--C语言实现 ] 复制带随机指针的链表(带视频讲解哦) _c语言

上下观古今，起伏千万途。这篇文章主要讲述[ 链表OJ题--C语言实现 ] 复制带随机指针的链表(带视频讲解哦)相关的知识，希望能为你提供帮助。

目录
题目来源：
实现代码：
思路分析：
实现步骤：
视频讲解：
题目来源：本来来源自：leetCode第138题. 复制带随机指针的链表
题目描述：

实现代码：

struct Node* copyRandomList(struct Node* head)
//1.拷贝原链表在其中间
struct Node* cur = head;
while(cur)

struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
newnode-> val = cur-> val;
newnode-> next = cur-> next;
cur-> next = newnode;
cur=cur-> next-> next;

//2.顺着原链表的random找到新链表中的random
cur = head;
while(cur)

struct Node* newnode = cur-> next;
if(cur-> random == NULL)

newnode-> random = NULL;

else

newnode-> random = cur-> random-> next;

cur = cur-> next-> next;

//3、将拷贝链表尾插到新链表
cur = head;
struct Node* copyhead = NULL,*copytail = NULL;
while(cur)

struct Node* copy = cur-> next;
struct Node* next =copy-> next;
copy-> next = next;
if(copytail == NULL)

copyhead = copytail = copy;

else

copytail-> next = copy;
copytail = copytail-> next;

cur = next;

return copyhead;

思路分析：本题由于原链表有random指针，拷贝原链表时也需将random指针进行拷贝，但是random指针的指向性是随机的，我们只能从原链表的random指针才能找到拷贝指针的random指针的指向。因此，本题的思路是：在原链表上进行拷贝，将拷贝链表插入原链表中，再让拷贝指针的random通过原链表的random指针找到其链表的指针，最后将拷贝链表从原链表中解下来，再将原链表复原即可。
实现步骤：1、拷贝原链表让拷贝链表插入原链表中，最终达到效果如下图所示。其中我们需要创建cur变量来控制原链表，创建newnode来控制拷贝链表，同时newnode由于是新拷贝出来的，因此需要重新开辟空间(malloc)。

2、通过原链表的random指针找到拷贝链表中指针的random指向。如下图所示，我们想要找到拷贝链表的random指针，只能通过原链表的random指针，由于我们将新链表插入原链表中，因此我们只需要让newnode的random指针指向原链表中的random的next指针即可满足。

【[ 链表OJ题--C语言实现 ] 复制带随机指针的链表(带视频讲解哦)】
注意：由于random指向性是随机的，原链表中的random也可能指向NULL，对于这种情况必须特殊分析，因为我们是找random的next指针，如果random只想空，我们再进行random的next操作，就相当于是对空指针进行操作，必定造成空指针异常。
3、将拷贝链表从原链表中解绑下来，并恢复原链表。此步骤可用尾插的方法将原链表解下，此类操作在之前的题中也多次使用。

此外：由于本题不考虑原链表环化，因此无需考虑环化。在将原链表尾插后一定要对原链表进行恢复。
视频讲解：https://www.bilibili.com/video/BV1oP4y1T7XG?spm_id_from=333.999.0.0

(本题完)