Leetcode 随即链表的深拷贝

题目链接：力扣

题目要求：

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/copy-list-with-random-pointer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

初步思路：将源节点一个一个尾插到新的链表中，之后通过遍历寻找random。但是由于malloc的特性，所以在新的链表中，每一个结点的地址都是不确定的，即使找到了原链表中结点对应的random，也很难体现在新链表中。如果对比值的话，出现两个相同的值就无法判断。如果对比地址又很难找到并且效率低下。

 

难点：找到对应的random的关系。怎么找到对应的random的关系呢？可以将新链表的每个结点插入到原链表中，这样一来，通过原链表random的对应关系，那么在新链表中也很容易找到了。

 

 

新思路：

①首先将原链表一个一个拷贝，然后将拷贝的每一个结点插入到原链表的两个结点中间。便于之后确定新链表的random

②将拷贝的新链表的random确定下来。copy->random=cur->random->next(找到了对应的结点之后需要在新链表中体现)

③将新链表拿下来尾插，之后恢复原链表的关系。

代码：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        struct Node*cur=head;
        while(cur)
        {
            struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
            copy->val=cur->val;
            copy->next=cur->next;
            cur->next=copy;

            cur=copy->next;
        }//插入

        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;
        }//找random

        cur=head;
        struct Node*copytail,*copyhead=NULL;
        while(cur)
        {
        struct Node*copy=cur->next;
        struct Node*next=copy->next;
            if(copytail==NULL)
            {
                copyhead=copytail=copy;
            }
            else
            {
              copytail->next=copy;
              copytail=copytail->next;
            }
            cur->next=next;
            cur=next;
            
        }

return copyhead;
    }
};