复制带随机指针的链表

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
• 掘金LV3用户 https://juejin.cn/user/1381426159953960
• 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
• 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目要求

链接：138. 复制带随机指针的链表 - 力扣（LeetCode） (leetcode-cn.com)

random指针指向自己也可以

思路：

思路1：直接拷贝原链表

原来的结点和复制出的结点没有关系 复制的结点是malloc出来的，二者没有直接的关系

如果需要找到拷贝结点对应的random结点->需要找到原来链表对应结点的random结点的距离k，然后对应指针走k步

每个结点都要如此！复杂

思路2： 时间复杂度:O(n)

• 1.复制结点，插入到原结点和下一个结点之间

  • 

代码：

   //1.拷贝结点，插入到原结点后面
    struct Node* cur = head;
    //cur遍历原链表，当cur为空时，说明已经遍历完原来的整个链表
    while(cur)
    {
        //开辟新节点拷贝cur指向结点的值
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        //拷贝值
        copy -> val = cur -> val;
        //将复制结点插入到原结点和下一个结点之间
        
        //copy链接原来结点的下一个结点,插入copy结点到原结点(cur)后面,
        copy -> next = cur->next;
        //cur指向的结点链接复制结点
        cur -> next = copy;
        //cur指向原来的下一个结点(下一个结点是：copy -> next 结点)
        cur = copy -> next;
    }

写法2：使用指针保存原来的下一个结点，双指针

struct Node* cur = head;
//cur遍历原链表，当cur为空时，说明已经遍历完原来的整个链表
while(cur)
{
    //开辟新节点拷贝cur指向结点的值
    struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
    copy->next = NULL;
    copy->random= NULL;
    copy->val = cur->val;
    
    //将复制结点插入到原结点和下一个结点之间
    struct ListNode* next = cur->next;//保存原来结点的下一个结点
    cur -> next = copy;//将复制结点插入到原结点之后
    copy->next = next;//复制结点链接原来结点的下一个结点
    cur = next;//cur指向原来结点的下一个结点，继续下一轮拷贝
}

• 2.根据原结点的random，处理复制结点的random

  • 

代码：

cur重新指向原来链表的头，遍历链表

按照思路2：

拷贝结点的random指针指向的结点，就是原来结点的random结点的下一个结点 因为我们是把拷贝结点，插入到原结点之后，所以就有了这种对应关系!

 //2.根据原结点，处理copy结点的random
    cur = head;
//遍历链表
    while(cur)
    {
        //copy结点在cur指向结点之后
        struct Node* copy = cur->next;
        //如果cur指向的结点的random为NULL(原来结点的random为NULL)，则拷贝结点的random也为NULL
        if(cur -> random  == NULL)
        {
            copy -> random = NULL;
        }
        else
        {
            //拷贝结点的random指向的就是cur的random结点的下一个结点
            copy -> random = cur -> random -> next;
        }
        cur = copy->next;
    }

• 3.将复制结点解下来，恢复原链表的关系

  • 

代码：

因为要返回拷贝链表的头，所以定义一个头指针

解下来->本质是尾插，为了方便，定义尾指针，可以用哨兵位，也可以不用

• 定义头尾指针，方便把拷贝结点尾插

• 保存原来结点的下一个结点(保存cur->next),记为next

• 把拷贝结点解下来，尾插到新链表

  • 先判断新链表是否为空，如果为空，头尾指针指向现在的拷贝结点
  • 否则：尾指针指向拷贝结点，然后更新尾指针的指向

• 恢复原来的结点的指向(cur指向的就是原来的结点)，cur的next指向next就是恢复指向

• 迭代往后走，直到把原链表遍历结束

 //3.把拷贝结点解下来，链接成新链表，同时恢复原链表
    //定义头指针和尾指针
    struct Node* copyHead = NULL,*copyTail = NULL;
    //cur遍历原链表
    cur = head;
    while(cur)
    {
        //复制的结点在当前cur指向结点的下一个位置
        struct Node* copy = cur->next;
        //原结点的下一个结点在拷贝结点的next，保存下一个结点
        struct Node* next = copy->next;
        //将拷贝链表解下来
        //最初：链表为空：判断一下
        if(copyTail == NULL)
        {
            copyHead  = copyTail = copy;
        }
        else
        {
            //链表的尾结点链接拷贝结点
            copyTail ->next = copy;
            //更新尾结点
            copyTail = copy;
        }
        //恢复原来结点的next指向
        cur->next = next;
        //cur指向原来结点的下一个结点，迭代往后走
        cur = next;
    }

代码

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
​
struct Node* copyRandomList(struct Node* head) 
{
    if(head == NULL)
    {
        return NULL;
    }
    //1.拷贝结点，插入到原结点后面
    struct Node* cur = head;
    //cur遍历原链表，当cur为空时，说明已经遍历完原来的整个链表
    while(cur)
    {
        //开辟新节点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        //拷贝值
        copy -> val = cur -> val;
        //copy链接原来结点的下一个结点,插入copy结点到原结点(cur)后面,
        copy -> next = cur->next;
        cur -> next = copy;
​
        //cur指向原来的下一个结点(此时是：copy -> next 结点)
        cur = copy -> next;
    }
    //2.根据原结点，处理copy结点的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        if(cur -> random  == NULL)
        {
            copy -> random = NULL;
        }
        else
        {
            copy -> random = cur -> random -> next;
        }
        cur = copy->next;
    }
    //3.把拷贝结点解下来，链接成新链表，同时恢复原链表
    struct Node* copyHead = NULL,*copyTail = NULL;
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if(copyTail == NULL)
        {
            copyHead  = copyTail = copy;
        }
        else
        {
            copyTail ->next = copy;
            copyTail = copy;
        }
        
        cur->next = next;
        cur = next;
    }
    return copyHead;
}

\