复制带随机指针的复杂链表

一、题目+题目链接

在这里插入图片描述

题目链接：https://leetcode.cn/problems/copy-list-with-random-pointer/

二、题目分析

这道题是要求我们复制给定的链表，给定的链表带有一个随机的指针random，该指针random的指向是不确定的方向的，并且不能破坏原来的链表结构。

三、解题思路

这道题的思路可以分成三步：

1、逐一复制原链表的结点，并在复制的同时把复制的结点链接在被复制结点的后面。

2、处理random的指向，由于每个复制的结点都在被复制结点的后面，所以复制结点的random就在被复制结点random的后一个。（最重要的一步）

3、分离复制的结点和被复制的结点并依次链接。

四、解题步骤

4.1 复制结点并链接到对应原节点的后面

定义三个指针cur，copy和next，按照以下方式复制结点并链接起来。当cur为NULL的时候就结束。

在这里插入图片描述
复制结束后的效果如下：

在这里插入图片描述

4.2 处理复制的结点的随机指针random

在这里插入图片描述

最核心的步骤是copy->random=cur->random->next,原因参考上面动图。

处理完之后的效果图如下：
在这里插入图片描述

cur为空就证明已经处理完了。

4.3 分离复制的链表结点和原链表结点并重新链接成为链表

在这里插入图片描述

分离后的效果图如下：
在这里插入图片描述

最后返回copyHead指针即可！！！

五、参考代码

typedef struct Node Node;
struct Node* copyRandomList(struct Node* head)
{
    if(head==NULL)
    {
        return NULL;
    }
    //1.复制链表
    Node* cur=head;
    while(cur)
    {
        Node* copy=(Node*)malloc(sizeof(Node));
        copy->val=cur->val;

        Node* next=cur->next;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }

    //2.处理random
    cur=head;
    while(cur)
    {
        Node* copy=cur->next;
        if(cur->random)
        {
            copy->random=cur->random->next;
        }
        else
        {
            copy->random=NULL;
        }

        cur=copy->next;
    }

    //3.拆
    cur=head;
    Node* copyHead=cur->next;
    while(cur)
    {
        Node* copy=cur->next;
        Node* next=copy->next;
        cur->next=next;
        if(next)
        {
            copy->next=next->next;
        }
        cur=next;
    }

    return copyHead;


}