Leetcode then a deep copy of the linked list

Topic link ： Power button

Subject requirements ：

Give you a length of n The linked list of , Each node contains an additional random pointer random , The pointer can point to any node or null node in the list .

To construct this linked list Deep copy . The deep copy should be made exactly by n individual new Node composition , The value of each new node is set to the value of its corresponding original node . New nodes next Pointers and random The pointer in the list should also point to the new node , And make these pointers in the original linked list and the copied linked list represent the same linked list state . The pointer in the copy linked list should not point to the node in the original linked list .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/copy-list-with-random-pointer
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

Preliminary ideas ： Insert the source nodes into the new linked list one by one , Then search through traversal random. But because of malloc Characteristics of , So in the new linked list , The address of each node is uncertain , Even if the corresponding node in the original linked list is found random, It is also difficult to reflect in the new linked list . If the contrast value , It is impossible to judge if there are two identical values . If the comparison address is difficult to find and inefficient .

 

difficulty ： Find the corresponding random The relationship between . How to find the corresponding random What about the relationship ？ You can insert each node of the new linked list into the original linked list , thus , Through the original linked list random Correspondence of , Then it's easy to find it in the new linked list .

 

 

New ideas ：

① First, copy the original linked list one by one , Then insert each node of the copy into the middle of the two nodes of the original linked list . It is convenient to determine the new linked list later random

② Will copy the new linked list random Make sure that .copy->random=cur->random->next( After finding the corresponding node, it needs to be reflected in the new linked list )

③ Take down the new linked list and insert it at the end , Then restore the relationship of the original linked list .

Code ：

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;
        }// Insert 

        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;
        }// look for 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;
    }
};