【链表面试题】——剑指 Offer ：复杂链表（带随机指针）的复制

文章目录

- 前言
- 1.题目介绍
- 2. 题目分析
- 3. 思路讲解
- - 思路1
  - 思路2
- 4. 分析图及源码展示

前言

这篇文章，我们一起来解决一道与链表相关的经典面试题：复杂链表（带随机指针）的复制。

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;
}