“This is the 18th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

Copy a linked list with a random pointer

The only idiot in the world is me, I forgot to choose C language, with C ++ results look at the wrong face mengbi

The title

Copy of this list to difficult place is random pointer random how to replicate his point, a lot of people really thought about the malloc node, I also thought of malloc a of a node, but the basic are all stuck in here, is how our chain, here we will again meet the gift of congenital bosses thinking ability to suppress, The last one was the suppression of spatial associations. (Come on, I like to be tempered by nature and nurture.)

thought

Ordinary copy

In fact, it’s pretty impressive to think about it. It’s kind of a prototype

ultimately(This is the real story of strange soldiers, the feeling of the secret)

He who takes off his trousers needs to lift them(This is a straight cut)

Code implementation

Cur is NULL is the time to stop copy

	struct Node* cur = head;
    if(! cur)return NULL;
    while(cur)
    {
        // Each time we malloc a copy node
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        // Start feeding data
        copy->val = cur->val;
        // Start inserting
        copy->next = cur->next;
        cur->next = copy;
        // start cur move
        cur = copy->next;
    }
Copy the code

Some people say why don’t you chain at the top of the Malloc node, because that’s when you’re still in school before the baby’s born? Yes, I’m going to secretly have a baby to keep you guys busy

 // Start random phase chain after copy
    cur = head;
    while(cur)
    {
        // Restore the node to copy for maintenance
        struct Node* copy = cur->next;
        if(cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;// The core code of the GIF above
        cur = copy->next;  
    }
Copy the code

And then you take it down one by one, you just go straight in and you restore the order of the original list

 // Start by inserting the tail one by one
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;
    cur = head;
    while(cur)
    {
        // Restore the node to copy for maintenance
        struct Node* copy = cur->next;
        // You need a next to restore the original list order. You can't run out of people and be irresponsible to them
        struct Node* next = copy->next;
        if(copyHead == NULL)
        {
            copyHead = copy;
            copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copy;
        }        
        cur->next = next;// This step depends on whether you are responsible for the original list
        cur = next;
    }
    return copyHead;
Copy the code

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
    if(! cur)return NULL;
    while(cur)
    {
        // Each time we malloc a copy node
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        // Start feeding data
        copy->val = cur->val;
        // Start inserting
        copy->next = cur->next;
        cur->next = copy;
        // start cur move
        cur = copy->next;
    }
    // Start random phase chain after copy
    cur = head;
    while(cur)
    {
        // Restore the node to copy for maintenance
        struct Node* copy = cur->next;
        if(cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;// The core code of the GIF above
        cur = copy->next;  
    }
    // Start by inserting the tail one by one
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;
    cur = head;
    while(cur)
    {
        // Restore the node to copy for maintenance
        struct Node* copy = cur->next;
        // You need a next to restore the original list order. You can't run out of people and be irresponsible to them
        struct Node* next = copy->next;
        if(copyHead == NULL)
        {
            copyHead = copy;
            copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copy;
        }        
        cur->next = next;// This step depends on whether you are responsible for the original list
        cur = next;
    }
    return copyHead;
}
Copy the code