【Leetcode】链表的深度拷贝——复制带随机指针的链表
做完了一些较为基础的题目后，会不会发现链表题目其实只要把图给画好了，逻辑理清晰，一切就会迎刃而解。如果有这种感觉的话，不妨来挑战一下下面这道来源于力扣上的一道题目：https://leetcode.cn/problems/copy-list-with-random-pointer（点击传送） 如下：
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。
分析： 这道题首先看到的第一感觉就是，哎呀我去，这么长的题目，让人眼花缭乱的，但其实这么多文字，我们根据底下的案例，提取关键因素就会发现，无非就是将原有链表给复制一份，同时原有链表的random指针是随机指向某一个节点的，复制链表的同时也要保证该节点的random指针指向的值与原有链表的random指向的值不变。
理解题目要求后我们该考虑应如何入手，这里有一种比较好的思路如下： 1、我们先将原有链表的每个节点都拷贝一份放在原节点的后面。如下：
2、我们发现，原节点的random随机指向的元素它的后面就是自己的拷贝节点，这说明了什么呢？我们第一步并没有处理random指针，但是我们可以发现，假如我们用cur遍历原链表，用tail遍历复制后的节点，cur->random->next节点，就是tail的random要找的节点。
就比如说，13的random是7，copy13的random就应该是7的next。 这样就保证了我们利用该规律可以使复制后的节点的random指向它应属于的位置。即，我们根据原链表的random指向的节点的下一个节点，就可以确定复制后的random应指向的节点。（空指针情况另行处理）
3、到了第三步，我们的复制后的链表节点的random已经处理完毕了，接下来我们将两个链表分割开来即可。
（图画的有点乱，大家自行根据分析或者后面的代码理解后去画图会很好理解）
最后便是代码的实现（一定要理清思路后再写，多画图）：
struct Node* copyRandomList(struct Node* head) {
//1、先将原链表的节点拷贝并连接在原节点后面
struct Node*cur=head;
while(cur)
{
//malloc拷贝的新节点
struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
struct Node*next=cur->next;
//将值放入拷贝的节点
copy->val=cur->val;
//连接所有节点
cur->next=copy;
copy->next=next;
cur=next;
}
//处理随机指针
//cur从head遍历，步长为2（即按照原链表进行遍历）
cur=head;
while(cur)
{
struct Node*tail=cur->next;
struct Node*next=tail->next;
//random不为空，根据原链表的random指向的节点的next来找到复制后的random指向的节点
if(cur->random!=NULL)
{
tail->random=cur->random->next;
}
//为空直接置空
else
{
tail->random=cur->random=NULL;
}
//cur步长为2
cur=next;
}
//分割链表（哨兵卫）
struct Node*newhead=(struct Node*)malloc(sizeof(struct Node));
newhead->next=NULL;
struct Node*tail=newhead;
//cur从head遍历，步长为2（即按照原链表进行遍历）
cur=head;
while(cur)
{
struct Node*next=cur->next;
tail->next=next;
tail=tail->next;
cur=next->next;
}
//哨兵卫的next才是有效数据，这里进行保存，为接下来的释放做准备，以免找不到哨兵卫的next
struct Node*phead=newhead->next;
//释放
free(newhead);
return phead;
}总结：多画图，理解题意即为制胜秘籍。
腾讯云开发者
