朋友们、伙计们，我们又见面了，本期来给大家解读一下LeetCode中第138道单链表OJ题，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！
数据结构与算法专栏：数据结构与算法
个 人 主 页 ：stackY、
C 语 言 专 栏：C语言：从入门到精通
编辑
LeetCode--138.复制带随即指针的链表：https://leetcode.cn/problems/copy-list-with-random-pointer/description/
目录
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; //链接拷贝节点的随机指针random if(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; //链接拷贝节点的随机指针random if(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; }
朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！
