【leetcode】随机链表的复制

大家好，我是苏貝，本篇博客带大家刷题，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️

点击查看题目

在这里插入图片描述

思路:

在这里插入图片描述

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur=head;
    //1.copy原链表并将其插入到原链表中
    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;
    }

    //2.将copy->random指向cur->random的下一个节点
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
        cur=cur->next->next;
    }

    //3.将copy的链表取下来
    cur=head;
    struct Node* newhead=NULL;
    struct Node* tail=NULL;
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;
        if(tail==NULL)
        {
            newhead=tail=copy;
        }
        else
        {
            tail->next=copy;
            tail=tail->next;
        }
        cur->next=next;
        cur=next;
    }
    if(tail)
        tail->next=NULL;
    return newhead;
}