单链表OJ题：LeetCode--138.复制带随即指针的链表

朋友们、伙计们，我们又见面了，本期来给大家解读一下LeetCode中第138道单链表OJ题，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

数据结构与算法专栏：数据结构与算法

个  人  主  页 ：stackY、

C 语 言 专 栏：C语言：从入门到精通

 LeetCode--138.复制带随即指针的链表：https://leetcode.cn/problems/copy-list-with-random-pointer/description/

目录

1.题目介绍

2.实例演示

3.解题思路

：：链接拷贝结点 ：： 

：：找拷贝节点的random ：：

：： 拆解拷贝链表 ：：

---

1.题目介绍

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

小编现在这里向大家袒露心扉一下：其实我刚刚看到这个单链表OJ题，看了半天连题目都没咋搞明白，好不容易看懂了题目介绍，可是又不知道该从何下手，然后求助各种大佬，才慢慢理解，然后整理思路，在这篇文章中将这道题分享给大家。

2.实例演示

3.解题思路

这道题应该算是单链表OJ题中比较复杂的一道题了，主要是比较难理解。题目的主要意思就是要拷贝出与原链表一模一样的一个链表。那么这道题拷贝链表都不是很复杂，比较难处理的就是这个随即指针random的指向，如果原链表的random指向空那这好说，拷贝链表的也指向空，但是如果原链表的random指向非空，那该如何去找这个random呢？在这里呢，很多老铁喜欢用random指向的值来比较，这种想法可以，但是架不住链表中有相同的值，那么就有许多老铁用它的random指向的地址来比较，这种方法是完全可行的，但是呢，这种暴力求解的方法往往都不是最优解，使用地址来进行比较的话它的时间复杂度是O(N^2)，效率也是不太行。所以我们需要寻求更优解。

这道题的解题思路我分为了三个步骤：

1. 链接拷贝结点：

 将拷贝结点插入到原结点的后面。

2. 找拷贝节点的random：

通过原链表来控制拷贝结点的随机指针random。

3. 拆解拷贝链表：

将拷贝结点拆下来，依次尾插组成新的链表，然后恢复原链表。

接下来我们一步一步来进行解题：

：：链接拷贝结点 ：： 

我们可以将拷贝结点链接在原结点的后面，这种方法比较巧妙，有助于我们找随即指针random。

先创建拷贝节点，然后遍历原链表，然后保存头节点的下一个结点，改变指向，将拷贝节点插入到原结点的后面。

图示：

 

代码演示：

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;//1.链接拷贝节点while(cur){//创建拷贝结点struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;//保存头指针的下一个结点struct Node* curNext = cur->next;//链接cur->next = copy;copy->next = curNext;cur = curNext;}//......
}

 ：：找拷贝节点的random ：：

当我们将拷贝结点链接在原结点的后面时，我们需要找拷贝结点的随机指针random，这里可以分为两种情况：

1. 如果原结点的random是空，那么直接将拷贝结点的random置为空即可。

2. 若不为空，那么就需要观察一下这个链表，拷贝结点的random指针指向的就是原结点的random指向的结点的next结点：

                               copy -> random = cur -> random -> next;

因为我们将拷贝结点链接在了原结点的后面，那么原结点的random指向的结点的next结点就是拷贝结点要找的random。我们依旧遍历整个链表，然后将拷贝节点的随机指针链接。

图示：

 

代码演示：

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;//1.链接拷贝节点while(cur){//创建拷贝结点struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;//保存头指针的下一个结点struct Node* curNext = cur->next;//链接cur->next = copy;copy->next = curNext;cur = curNext;}//2.找拷贝节点的random //重新返回头cur = head;while(cur){//找拷贝结点struct Node* copy = cur->next;//找下一个结点struct Node* next = copy->next;//链接拷贝节点的随机指针randomif(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}//遍历cur = next;}//......
}

：： 拆解拷贝链表 ：：

我们找到了拷贝链表之后呢，需要将这些拷贝的结点组成一个新的链表，这就需要将这些拷贝结点依次进行尾插，然后再将原链表恢复。这就比较简单了：

图示：

 完整代码演示：

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;//1.链接拷贝节点while(cur){//创建拷贝结点struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;//保存头指针的下一个结点struct Node* curNext = cur->next;//链接cur->next = copy;copy->next = curNext;cur = curNext;}//2.找拷贝节点的random //重新返回头cur = head;while(cur){//找拷贝结点struct Node* copy = cur->next;//找下一个结点struct Node* next = copy->next;//链接拷贝节点的随机指针randomif(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}//遍历cur = next;}//3.拆解拷贝结点，恢复原链表//重新返回头cur = head;//创建新的链表struct Node* copyHead = NULL;struct Node* copyTail = NULL;while(cur){//找拷贝结点struct Node* copy = cur->next;//找下一个结点struct Node* next = copy->next;//尾插拷贝节点构成新的链表if(copyTail == NULL){copyHead = copyTail = copy;}else{copyTail->next = copy;copyTail = copyTail->next;}//恢复原链表cur->next = next;cur = next;}return copyHead;}

 

朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！