【初阶数据结构】——剑指 Offer ： 复杂链表（带随机指针）的复制
【初阶数据结构】——剑指 Offer ： 复杂链表（带随机指针）的复制
前言
这篇文章，我们一起来解决一道与链表相关的经典面试题：复杂链表（带随机指针）的复制。
1.题目介绍
我们先来一起了解一下这道题：
这道题是《剑指offer》上的一道经典题目：
在力扣上也有原题： 链接: link 这篇文章，就给大家详细讲解一下这道题。
我们一起来看一下题目：
题目呢，看起来还挺长的。
但是我们不能上去被题目就吓到了，其实这个题目就是让我们复制链表嘛，给我们一个链表，我们要自己再创建一个和它一样的链表就行了嘛。
🆗，那接下来，我们就来一起分析一下这道题。
2. 题目分析
那既然这道题是让我们复制链表的，那我们就先来思考一下应该如何复制？
通过前面的学习，我们已经学会了如果创建一个链表，那复制的话，就是创建一个一模一样的链表嘛。
我们就拿一个题目给出的输入样例来分析一下：
那要复制这样一个链表，是不是好像也不难啊。
它有5个结点，我们就创建的链表也带5个结点就行了嘛，每个结点1个数据域，2个指针域，next指针依次存下一个结点的地址。 对吧，这些操作好像都不难。
那求解这道题的关键之处或者说难点在哪呢？
是不是就麻烦在这个随机指针的问题啊，这是不是比较难搞啊。 每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 我们除了要把链表的连接关系复制出来，每个结点的随机指针指向哪里，我们也要复制出来的。 但是每个结点的随机指针的指向随机的，可能指向空，或者是任意一个结点，那我们要复制随机指针，就必须知道每个结点的随机指针的指向，这就不好搞了。
我们看是很容易看出来的，但是如何让我们的程序面对不同的输入，都能正确找到每一个结点随机指针的指向，并进行复制呢？
3. 思路讲解
思路1
首先思路1就是暴力求解：
复制随机指针的时候，每个复制结点的random指针，我们都要一一去寻找它对应的源结点指向的是第几个结点（如果指向空是比较好搞的），然后让复制结点也指向对应的结点，但是注意不能看它指向的数值是几，因为不同结点数据域的数值可能是一样的。
但是这种解法时间复杂度是O(N^2) ，不是太好，我们就不实现了。
接下来我们再讲另外一种比较优的算法。
思路2
这个思路是什么呢？需要我们做三件事情：
- 创建拷贝结点链接到源链表每一个结点的后面
那这么做有什么目的呢？ 这里先不解释，等到下一步操作时我们就知道为什么要这么做了。
那这一步代码要如何实现呢？
那也很简单，循环对链表进行遍历，每次循环都创建一个copy结点，copy结点的数据域的值和源节点相同，然后连接到源结点后面，一次向后直到遍历结束。
struct Node* cur=head;
//拷贝结点到源节点后面
while(cur)
{
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
//链接
copy->next=cur->next;
cur->next=copy;
//cur往后走
cur=copy->next;
}接下来是第二步：
- 设置拷贝结点的random指针域
这么设置呢？
如果源结点的random域为空，则拷贝结点的random域也直接置为空；如果不为空，拷贝结点的random域指向 【其对应源节点的random域指向的源节点】的next对应的拷贝结点。
大家可以结合图理解一下这一步的操作。 这样拷贝结点的random指针设置起来是不是就很方便了，这也是我们第一步把拷贝结点链接在源节点后面的原因。
cur=head;
//设置拷贝结点的random域
while(cur)
{
struct Node* copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=copy->next;
}那接下来就是第3步，也是最后一步了。
- 第三步:将拷贝结点解绑下来，链接组成最终要返回的拷贝链表
经过前面两步的努力，拷贝链表的所有结点都已经存在了，而且它们的随机指针random也设置好了，那现在我们把所有的拷贝结点从源链表上解下来，再组成一个完整的链表不就完成了吗？当然因为前两步的操作我们改变了原链表，所以最后最好将它还原一下，避免题目测试的时候会检查原链表是否被改变了。
那要将所有结点组成链表，我们就可以依次尾插。
这里给不给头结点都可以，我们这里选择不给头结点，不过这样第一个结点尾插进行一次判断就行了。
//将拷贝结点解下尾插成新链表
cur=head;
struct Node* copyhead=NULL;
struct Node* copytail=NULL;
while(cur)
{
struct Node* copy=cur->next;
//将原链表还原
cur->next=copy->next;
//尾插
if(copytail==NULL)
{
copyhead=copytail=copy;
}
else
{
copytail->next=copy;
copytail=copy;
}
//cur向后走
cur=copy->next;
}拷贝链表创建好，最好作为函数返回值返回就行了。
4. 分析图及源码展示
源码：
struct Node* copyRandomList(struct Node* head) {
struct Node* cur=head;
//拷贝结点到源节点后面
while(cur)
{
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
//链接
copy->next=cur->next;
cur->next=copy;
//cur往后走
cur=copy->next;
}
cur=head;
//设置拷贝结点的random域
while(cur)
{
struct Node* copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=copy->next;
}
//将拷贝结点解下尾插成新链表
cur=head;
struct Node* copyhead=NULL;
struct Node* copytail=NULL;
while(cur)
{
struct Node* copy=cur->next;
//将原链表还原
cur->next=copy->next;
//尾插
if(copytail==NULL)
{
copyhead=copytail=copy;
}
else
{
copytail->next=copy;
copytail=copy;
}
//cur向后走
cur=copy->next;
}
return copyhead;
}🆗，那这道题的讲解就完了，希望能帮助到大家。 如果有写的不好的地方，欢迎大家指正！！！