当前位置：首页 > article >正文

单链表的“影分身术”：随机指针链表的深度拷贝实现

article 2025/2/5 8:30:39

题目如下：

随机链表的复制：

在这里插入图片描述

解题过程如下：

里面的一个括号表示一个结点，包括结点存储的数值val、random指针，这里的random表示下标（从0开始）next指针不用给出来，因为next指针始终指向下一个结点：

在这里插入图片描述

题干提到了深拷贝，有深拷贝就有浅拷贝，那么就来说说什么是深/浅拷贝吧~
浅拷贝也就是值拷贝。例如，（函数的传值调用）；还比如，浅拷贝当前的结点，那么两个指针pcur、repeat都指向这个结点：

在这里插入图片描述

深拷贝就是只有地址不一样的两个空间。比如，深拷贝一个结点，那么就要向操作系统申请一个结点大小的空间，两个结点的大小、结点里的数值、next指针一样，只有地址不一样：

在这里插入图片描述

若创建新链表，random指针不好设置，因为random指针要指向链表中的任何结点或空结点。

思路：

在原链表基础上深拷贝结点并插入在原链表中

在这里插入图片描述

设置random指针

在这里插入图片描述

断开新旧链表

在这里插入图片描述

写完代码后，发现会有对空指针的解引用的风险：

在这里插入图片描述

完整代码如下：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
Node* buyNode(int x)
{
    Node* newnode = (Node*)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = newnode->random = NULL;
    return newnode;
}
void AddNode(Node* head)
{
    Node* pcur = head;
    while (pcur)
    {
        Node* newnode = buyNode(pcur->val);
        Node* next = pcur->next;
        newnode->next = pcur->next;
        pcur->next = newnode;
        pcur = next;
    }
}
void setRandom(Node* head)
{
    Node* cur = head;
    while (cur)
    {
        Node* copy = cur->next;
        if (cur->random)
            copy->random = cur->random->next;
        cur = copy->next;        
    }
}
struct Node* copyRandomList(struct Node* head) {
    //若链表为空
    if (head == NULL)
    {
        return head;
    }
	//深拷贝原链表中的结点并插入到原链表中
    AddNode(head);
    //设置random指针
    setRandom(head);
    //断开新旧链表
    Node* pcur = head;
    Node* copyHead, *copyTail;
    copyHead = copyTail = pcur->next;
    while (copyTail->next)
    {
        pcur = copyTail->next;
        copyTail->next = pcur->next;
        copyTail = copyTail->next;
    }
    return copyHead;
}