【LeetCode&数据结构】随机链表的复制

用户11831438

发布于 2025-12-30 13:52:05

460

随机链表的复制问题

138. 随机链表的复制 - 力扣（LeetCode）

1、题目描述和示例

2、思路

我们的思路是： 1、在原链表的基础上拷贝结点 2、设置random指针 3、断开新旧链表

我们先来看一下题目描述——

嗯？什么是深拷贝？ 看下图：

所谓的深拷贝就是重新向系统申请一个空间，然后用此空间对pcur中的值进行拷贝，地址不同

有了深拷贝，还有浅拷贝：

浅拷贝：值的拷贝，不需要重新申请空间，地址相同

3、解题过程

在做算法题的时候，画图是很重要的

如下图所示——

random如何设置？

4、改进措施

既然我们创建一个新链表，并在新链表中设置random指针很麻烦，那我们可以在原链表中操作

1.在原链表的基础上拷贝结点

2.设置random指针

3.断开新旧链表

变成这样——

ok，我们将上面的思路用代码来试一下：

 typedef struct Node Node;
 //申请结点空间
 Node* BuyNode(int num)
 {
    Node* newnode=(Node*)malloc(sizeof(Node));
    newnode->val=num;
    newnode->next=NULL;
    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=next;
        pcur->next=newnode;
        pcur=next;
    }
}
void setRandom(Node* head)
{
    Node* pcur=head;
    while(pcur)
    {
        Node* copy=pcur->next;
        if(pcur->random)
        {
            copy->random=pcur->random->next;
        }
        pcur=copy->next;
    }
}
struct Node* copyRandomList(struct Node* 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;
}

运行一下：

出现了对空指针的报错~~~那就说明在该代码中存在对空指针的使用

改进代码：

 typedef struct Node Node;
 //申请结点空间
 Node* BuyNode(int num)
 {
    Node* newnode=(Node*)malloc(sizeof(Node));
    newnode->val=num;
    newnode->next=NULL;
    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=next;
        pcur->next=newnode;
        pcur=next;
    }
}
void setRandom(Node* head)
{
    Node* pcur=head;
    while(pcur)
    {
        Node* copy=pcur->next;
        if(pcur->random)
        {
            copy->random=pcur->random->next;
        }
        pcur=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;
}

ok，通过上面的操作，我们就可以完成这道算法题啦！！！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-30，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构