目录

一、题目介绍

​编辑

二、题目分析

三、代码实现

题目链接：138. 复制带随机指针的链表 - 力扣（LeetCode）

一、题目介绍

我们最一开始看到题目可能会没有思路，或者压根就不知道如何下手

下面我将提出一种简便的算法来解决这道题

二、题目分析

我们可以先将每一个节点都复制一份，然后将复制节点插入到原节点的后面

将每个复制节点的val都置为原节点的值，同时先不要修改复制节点的random，让它为随机值就好

如果我们在给复制节点的val赋值的同时将random也赋值，这个random

指针会指向原链表，而不会指向我们复制之后的链表，因为前面节点的random有可能会指向后面的节点，可是那个节点我们还没有复制出来，所以我们需要遍历链表两遍来处理复制链表节点

然后就剩下最后一步了，将复制节点从链表上取下来

为了方便我们可以使用哨兵位的头节点来进行尾插，返回哨兵位头节点的next

三、代码实现

struct Node* copyRandomList(struct Node* head) {
    if(head==NULL)
    {
        return head;
    }
	struct Node*cur=head;
    //链接节点
    while(cur)
    {
        struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
        struct Node*next=cur->next;
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }
    //处理random
    cur=head;
    while(cur)
    {
        struct Node*copy=cur->next;
        struct Node*next=copy->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;

        }
        else
        {
            copy->random=cur->random->next;
        }

       cur=next;
    }

    //尾插形成新链
    cur=head;
    struct Node*newHead=(struct Node*)malloc(sizeof(struct Node));
    struct Node*tail=newHead;
    while(cur)
    {
        struct Node*copy=cur->next;
        struct Node*next=copy->next;
        tail->next=copy;
        tail=copy;
        cur=next;
    }
    return newHead->next;
}

同时要注意，我们使用的是copy->random=cur->random->next;这条语句，如果cur的random指向的是NULL，我们在去访问NULL->next就会出现空指针的问题，这一点必须要注意

同时这段代码还有一个比较大的问题，我们malloc了一个newHead，我们没有free掉它，会出现内存泄漏的问题

因此我们这样修改

struct Node* copyRandomList(struct Node* head) {
    if(head==NULL)
    {
        return head;
    }
	struct Node*cur=head;
    //链接节点
    while(cur)
    {
        struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
        struct Node*next=cur->next;
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }
    //处理random
    cur=head;
    while(cur)
    {
        struct Node*copy=cur->next;
        struct Node*next=copy->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;

        }
        else
        {
            copy->random=cur->random->next;
        }

       cur=next;
    }

    //尾插形成新链
    cur=head;
    struct Node*newHead=(struct Node*)malloc(sizeof(struct Node));
    struct Node*tail=newHead;
    while(cur)
    {
        struct Node*copy=cur->next;
        struct Node*next=copy->next;
        tail->next=copy;
        tail=copy;
        cur=next;
    }
    struct Node*ret=newHead->next;
    free(newHead);
    return ret;

}

这样就过了

虽然我们在做oj题时，它不会报错，但是为了安全起见，我们必须手动释放malloc出的变量