C语言编程实战：每日一题：随机链表的复制

题目：随机链表的复制

• LeetCode:随机链表的复制

一、思路解析

该代码采用 “原地复制+拆分” 策略，高效实现复杂链表（每个节点含val、next指针、random指针）的深拷贝，核心优势是 时间复杂度O(n)、空间复杂度O(1)（不考虑目标链表存储空间），具体分3步：

1. 第一步：原地插入拷贝节点（构建“原节点-拷贝节点”成对结构）

• 遍历原链表的每个节点pcur，为其创建一个拷贝节点NewNode（值与原节点相同，random初始为NULL）。
• 将拷贝节点插入到原节点的后面（即NewNode->next = pcur->next，再pcur->next = NewNode）。
• 最终原链表结构变为：原节点1 -> 拷贝节点1 -> 原节点2 -> 拷贝节点2 -> ... -> 原节点n -> 拷贝节点n -> NULL。

2. 第二步：设置拷贝节点的random指针

• 再次遍历原链表（仅遍历原节点，步长为2：pcur = pcur->next->next）。
• 对于每个原节点pcur，其拷贝节点是pcur->next：
  • 若原节点pcur的random为NULL，则拷贝节点的random也为NULL；
  • 若原节点pcur的random指向原链表中的某节点A，则拷贝节点的random应指向A的拷贝节点（即A->next），这是该方法的核心巧思（利用第一步构建的成对结构，直接通过原节点的random找到拷贝节点）。

3. 第三步：拆分原链表与拷贝链表

• 原链表的第一个拷贝节点（head->next）即为新链表的头节点Newhead。
• 遍历拷贝链表（步长为2：pcur = pcur->next->next），将拷贝节点的next指针指向下一个拷贝节点（跳过原节点），最终拆分出独立的拷贝链表。
• 原链表结构在拆分后会恢复（可选，该代码未显式恢复，但不影响拷贝结果）。

二、流程图

三、关键

1. BuyNode函数作用：封装拷贝节点的创建逻辑，确保拷贝节点的next初始指向原节点的下一个节点，random初始为NULL。
2. random指针设置的核心：利用“原节点后紧跟拷贝节点”的结构，原节点A的random指向B，则拷贝节点A'的random必然指向B'（B->next）。
3. 拆分逻辑：拷贝链表的节点在原链表中是“隔一个”存在的，因此只需将每个拷贝节点的next指向其下一个拷贝节点（pcur->next->next）即可拆分出独立的拷贝链表。

四、代码

typedef struct Node Node;
Node* BuyNode(int x,Node* pcur)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));
    NewNode->val = x;
    NewNode->next = pcur->next;
    NewNode->random = NULL;
    return NewNode;
}
struct Node* copyRandomList(struct Node* head) 
{
    if(head == NULL)
    {
        return NULL;
    }
    Node* pcur = head;
	while(pcur)
    {
        Node* NewNode = BuyNode(pcur->val,pcur);
        Node* prev = pcur;
        pcur = pcur->next;
        prev->next = NewNode;
    }
    pcur = head;
    while(pcur != NULL && pcur->next != NULL)
    {
        Node* pcopy = pcur->next; 
        if(pcur->random == NULL)
        {
            pcopy->random = NULL;
        }
        else
        {
            pcopy->random = pcur->random->next;
        }
        pcur = pcur->next->next;
    }
    Node* Newhead = head->next;
    pcur = Newhead;
    while(pcur!= NULL && pcur->next != NULL)
    {
        pcur->next = pcur->next->next;
        pcur = pcur->next;
    }
    return Newhead;
}

• 本节完…