链表掌握九成？这题能独立完成吗

若能独立完成本题的思路构建与代码实现，说明你对链表的理解已掌握九成。建议先自行尝试解题（题目链接见下图），以检验掌握程度。若遇到困难，可参考本文提供的详细思路解析和代码实现（采用C语言）。

随机链表的复制

链接：https://leetcode.cn/problems/copy-list-with-random-pointer

本题难点在于如何拷贝randon,怎样才能找到拷贝链表和原链表的关联。

解题思路：

此题可以分三步进行：

1.拷贝链表的每一个节点，拷贝的节点先链接到被拷贝节点的后面

节点复制阶段遍历原始链表，为每个节点创建拷贝节点，将拷贝节点插入到原始节点之后。例如原始链表为A->B->C，复制后变为A->A'->B->B'->C->C'。这样我们就将拷贝链表和原链表关联起来，对我们后续找链表里的数据至关重要。

2.复制随机指针的链接：拷贝节点的随机指针指向被拷贝节点随机指针的下一个位置

随机指针设置阶段再次遍历链表，处理每个拷贝节点的random指针。由于第一步我们将拷贝节点和原连接起来，变成A->A'->B->B'->C->C'。由图我们可以看出节点原始节点的random指针指向的节点的下一个节点即为拷贝节点应该指向的位置。若原始节点的random为NULL，拷贝节点的random也设为NULL。

3.拆解链表，把拷贝的链表从原链表中拆解出来

链表拆分阶段创建拷贝链表的头指针和尾指针，通过遍历将拷贝节点从交错链表中提取出来，同时恢复原始链表的连接关系。每次处理将拷贝节点接入拷贝链表尾部，并移动原始链表的当前指针。最终返回副本链表的头节点。

该算法时间复杂度为O(n)，空间复杂度为O(1)（不计入返回的深拷贝链表所需空间），通过巧妙地利用节点交错排列避免了哈希表的额外空间开销。

代码实现：

struct Node* copyRandomList(struct Node* head) { /* 解题步骤： 1. 为每个节点创建副本，插入到原节点之后 2. 设置副本节点的random指针 3. 分离原链表和副本链表 */ 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 = copy->next; } // 第二步：设置副本节点的random指针 cur = head; while(cur) { struct Node* copy = cur->next; copy->random = cur->random ? cur->random->next : NULL; cur = copy->next; } // 第三步：分离两个链表 cur = head; struct Node* copyhead = NULL, *copytail = NULL; while(cur) { struct Node* copy = cur->next; cur->next = copy->next; if(!copytail) { copyhead = copytail = copy; } else { copytail->next = copy; copytail = copy; } cur = cur->next; } return copyhead; }

如果对你有帮助别忘了一键三连，制作不易谢谢支持！