【链表经典面试题】LeetCode138.复制带随机指针的链表（链表深拷贝）

📇文章目录

🚀题目描述
🚀思路1：
🚀思路2：
🚀完整代码

🚀题目描述

在这里插入图片描述

解读：题目意思就是给你一个链表这个链表中除了有next指针之外还有一个指向这个链表的随机位置的一个指针，让你复制这一个链表
而你复制之后的这个链表中的每一个节点的随机指针，也应该像原链表一样指向对应的节点

这里容易有一个误区，就是把拷贝之后的节点的随机指针random 置成原链表的random,这是不对的，因为他的意思是相当于让你把链表的结构也复制过来
比如说
原链表是7->13->11>10->1 ，其中13的random指向的是原链表中的7
那么你拷贝之后的链表也是 7->13->11->10->1 并且13指向拷贝之后的链表中的7

那么具体怎么做呢？
主要难搞的就是这个random

🚀思路1：

7->13->11->10->1这个链表为例
复制之后我的13节点的random应该指向7 那么我遍历一遍去找值为7的节点不就可以了吗？
但是我们要想一想
如果这个链表是 7->7->13->11->10>1呢？
有两个节点的值都是7 ，那么返回哪一个呢？是不是就不行了！
而且在效率方面最坏的情况，每一个节点都需要遍历一遍
时间复杂度是O(N^2)
所以这是一种错误思路！（怕就怕他有不止一个相同的值）

🚀思路2：

（想不到就没法做！！），技巧性很强，所以先看步骤

每一个拷贝的节点都直接链接在原节点的后面，形成一个大链表（考察链表节点的插入）
然后通过原节点的random去找拷贝节点的random
复制节点的random 就等于原节点的random的next（考察逻辑）
如图分析

分析：拷贝链表中的random肯定和原链表中的random是有关系的，那么关系是什么呢？
拷贝链表中的random一定指向了拷贝链表中的某一个节点
这个节点怎么找呢？
这就需要借助原链表
因为我们把原链表和拷贝链表已经连接起来了，并且每一个拷贝节点是原链表的相同节点的next
我们还是拿13这个节点为例，看上图
原链表13的random指向的位置的下一个就是与原链表13的random指向的节点的拷贝（注意理解这句话！！）
之所以这么做是因为：拷贝链表的random要指向自己所在的链表的节点！
所以拷贝节点的random就是原节点的random指向的next
如果cur的random为空，那么拷贝链表的random也为空

3.合并之后的链表拆分下来（考察链表的删除和尾插）
如图：在这里插入图片描述
也就是重新遍历一遍合并后的大链表
以cur指向原链表，每一次循环都定义一个copy节点等于cur的next
把copy节点尾插到新的头并把原链表中的相邻节点连接起来（相当于删除pos位置然后链接前后节点）

🚀完整代码

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur=head;
    //1. 拷贝原链表的值 并且链接原链表
    while(cur)
    {
        //每一次都malloc一个新节点出来，把新节点和原链表连接起来
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        struct Node* next=cur->next;
        //copy的值 是cur的值
        copy->val=cur->val;
        //然后链接 cur copy next
        cur->next=copy;
        copy->next=next;
        //然后让cur向后走
        cur=next;

    }


    //2. 然后拷贝random指针
    
    cur=head;//让cur重新指向head
    while(cur)
    {
        //因为已经链接上了原链表
        // 所以每一次进来可以利用cur找到copy
        struct Node* copy=cur->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;;
        }
        else
        {
            copy->random=cur->random->next;
        }
        //然后更新cur
        cur=copy->next;
    }

    //3. 把原链表和拷贝链表分离开
    cur=head;
    struct Node* copyNhead=NULL,*copyTail=NULL;
    while(cur)
    {
        //每一次找到我的拷贝链表
        struct Node*copy=cur->next;
        // 拷贝链表的下一个（用于恢复原链表（链接原链表的两个节点））
        struct Node*next=copy->next;
        //如果新链表尾为空 那么就头插
        if(copyTail==NULL)
        {
            copyTail=copyNhead=copy;
        }
        else
        {
            // 如果拆出来的拷贝链表不为空 
            // 那么 tail的next赋值为copy
            // 然后 更新尾
            copyTail->next=copy;
            copyTail=copy;

        }
        // 然后cur向后走
        cur->next=next;//这是恢复原链表
        cur=next;
    }
    return copyNhead;

}