深度剖析：复制带随机指针的链表算法实现
在链表相关的算法中，复制一个带有随机指针的链表是一个经典且具有一定难度的问题。本文将深入分析一段用C语言实现的复制带随机指针链表的代码，通过模块化的方式详细解释每段代码的作用，帮助读者更好地理解这一复杂算法。
作者主页：共享家9527-CSDN博客
代码仓：Study in the first semester of college.c: 大一下学期学习，主要内容为个人学习过程记录
2025寒假C语言学习: 学习记录
链表节点定义
c
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
这段代码定义了链表节点的结构。每个节点包含三个成员：一个整数值 val ，一个指向下一个节点的指针 next ，以及一个指向链表中任意节点（或NULL）的随机指针 random 。这个定义是后续链表操作的基础。
复制链表主体函数
c
struct Node* copyRandomList(struct Node* head) {
// 若为空链表，直接返回NULL
if(!head) return NULL;
函数 copyRandomList 接收链表的头指针 head 作为参数，返回复制后的链表头指针。首先进行边界条件检查，如果原链表为空（ head 为NULL），则直接返回NULL，因为没有节点需要复制。
第一步：在原链表每个节点后添加复制节点
c
// 在与原链表的每个节点后添加复制一个节点
struct Node* node = head;
while(node){
struct Node* newNode = malloc(sizeof(struct Node));
newNode->val = node->val;
newNode->next = node->next;
newNode->random = NULL;
node->next = newNode;
node = node->next->next;
}
这部分代码的作用是在原链表的每个节点后面插入一个复制节点。具体步骤如下：
1. 初始化一个指针 node 指向原链表的头节点。
2. 使用 while 循环遍历原链表。
3. 对于每个节点，分配内存创建一个新节点 newNode 。
4. 将原节点的值 val 复制到新节点。
5. 新节点的 next 指针指向原节点的下一个节点。
6. 新节点的 random 指针初始化为NULL。
7. 将原节点的 next 指针指向新节点，从而将新节点插入到原节点之后。
8. 更新 node 指针，跳过新插入的节点，指向下一个原节点。
第二步：为复制节点的random指针赋值
c
// 为所有复制的节点的random赋值
node = head;
while(node){
// 若原节点的random不为空，赋值
if(node->random){
node->next->random = node->random->next;
}
node = node->next->next;
}
在这一步中，再次遍历链表，为所有复制节点的 random 指针赋值。因为复制节点紧跟在原节点之后，所以 node->next 就是复制节点。如果原节点的 random 指针不为NULL，那么原节点 random 指向节点的下一个节点就是复制节点 random 应该指向的节点（即 node->random->next ）。
第三步：分离新链表和原链表
c
// 分离新节点和旧节点
struct Node* newHead = head->next;
struct Node* pre = head;
struct Node* cur = head->next;
while(pre->next->next){
pre->next = cur->next;
cur->next = cur->next->next;
pre = pre->next;
cur = pre->next;
}
pre->next = NULL;
return newHead;
最后一步是将新链表从交错的链表结构中分离出来。具体操作如下：
1. 初始化 newHead 为新链表的头节点，即原链表头节点的下一个节点。
2. 使用 pre 指向原链表节点， cur 指向新链表节点。
3. 通过 while 循环，不断调整 pre 和 cur 的 next 指针，将原链表和新链表分离。
4. 当原链表只剩下最后一个节点时，将 pre 的 next 指针设为NULL，完成原链表的修复。
5. 最后返回新链表的头指针 newHead 。
通过以上三个步骤，成功实现了对带随机指针链表的复制。这种方法巧妙地利用了原链表的结构，在不使用额外复杂数据结构（如哈希表）的情况下完成了复制操作，时间复杂度为O(n)，空间复杂度为O(1)。