​

1. 题目描述

2. 思路分析

此题可以分三步进行：

1. 拷贝链表的每一个结点，拷贝的结点先链接到被拷贝结点的后面。
2. 复制随机指针的链接：拷贝结点的随机指针指向被拷贝结点随机指针的下一个位置。
3. 拆解链表，把拷贝的链表从原链表中拆解出来。

3. 代码实现

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
   
   
    struct Node* cur=head;
    while(cur)
    {
   
   
        struct Node* next=cur->next;
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        cur=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;
    }
    cur=head;
    struct Node* copyhead=NULL,*copytail=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;
}

​