[ Linked list OJ question 9 ] Copy the linked list with random pointers — with video explanation~~

Hits: 0

Table of contents

Topic source:

Implementation code:

Thought analysis:

Implementation steps:

Video explanation:

Topic source:

138. Copy a linked list with random pointers – LeetCode (leetcode-cn.com)

Topic description:

Implementation code:

struct Node* copyRandomList(struct Node* head) {
     //1. Copy the original linked list in the middle
    struct Node* cur = head;
    while(cur)
    {
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->val = cur->val;
        newnode->next = cur->next;
        cur->next = newnode;
        cur=cur->next->next;
    }
    //2. Follow the random of the original linked list to find the random in the new linked list
    cur = head;
    while(cur)
    {
        struct Node* newnode = cur->next;
        if(cur->random == NULL)
        {
            newnode->random = NULL;
        }
        else
        {
            newnode->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    //3. Insert the tail of the copied linked list into the new linked list
    cur = head;
    struct Node* copyhead = NULL,*copytail = NULL;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next =copy->next;
        copy->next = next;
        if(copytail == NULL)
        {
            copyhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;
            copytail = copytail->next;
        }
        cur = next;
    }
    return copyhead;
}

Thought analysis:

In this question, since the original [linked list] has a random pointer, the random pointer needs to be copied when copying the original linked list, but the pointing of the random pointer is random. We can only find the random pointer of the copied pointer from the random pointer of the original linked list. Therefore, the idea of ​​​​this question is : copy on the original linked list, insert the copied linked list into the original linked list, then let the random pointer of the copied pointer find the pointer of its linked list through the random pointer of the original linked list, and finally untie the copied linked list from the original linked list, Then restore the original list.

Implementation steps:

  1. Copy the original linked list and insert the copied linked list into the original linked list. The final effect is shown in the figure below. Among them, we need to create a cur variable to control the original linked list, and create a newnode to control the copy linked list. At the same time, since the newnode is newly copied, it needs to re-open space ( [malloc] ).

  2. Find the random pointer of the pointer in the copy linked list through the random pointer of the original linked list. As shown in the figure below, if we want to find the random pointer of the copied linked list, we can only use the random pointer of the original linked list. Since we insert the new linked list into the original linked list, we only need to let the random pointer of newnode point to the random pointer in the original linked list. The next pointer suffices. 

Note: Since the random pointing is random, the random in the original linked list may also point to NULL. Special analysis is required for this situation, because we are looking for the next pointer of random. If random only wants to be empty, we will perform the next operation of random. , which is equivalent to operating on a null pointer, which must result in a null pointer exception.

  1. Unbind the copied linked list from the original linked list and restore the original linked list. In this step, the original linked list can be solved by the method of tail insertion. Such operations have also been used many times in the previous questions.

In addition: Since this question does not consider the circularization of the original linked list, there is no need to consider circularization. After inserting the tail of the original linked list, the original linked list must be restored.

Video explanation:

C language Leetcode 138 questions copy linked list with random pointer

(End of this question)

Leave a Reply

Your email address will not be published.