力扣：随即指针138. 复制带随机指针的链表

分析：
该题的大致题意就是有一个带随机指针的链表，复制这个链表但是不能指向原链表的节点，所以每一个节点都要复制一遍
大神思路：
ps:我是学来的

上代码：

struct Node* copyRandomList(struct Node* head)
{
    //1.在原链表每个节点的后面复制一个节点
   struct Node* cur = head;
    while(cur)
    {
        //插入
        struct Node*copy = (struct Node*)malloc(sizeof(struct Node));
        if(copy == NULL)
        {
            perror("malloc\n");
            return NULL;
        }
        copy->val = cur->val;
        struct Node* next = cur->next;
        cur->next = copy;
        copy->next = next;
        //迭代
        cur = next;
    } 
    //2.处理random
    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;//迭代
    }
    //3.恢复原链表，链接新链表  删除＋尾插 
    cur=head;
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;//用来还原原链表
    //尾插：链接新链表
        //空链表（第一次尾插）
        if(copyhead == NULL)
        {
            copyhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;//尾插
            copytail = copytail->next;//迭代 
        }
        
    //删除：恢复原链表
        //free(cur->next);//此处不用free
        cur->next = next;

        cur = cur->next;//迭代
    }
   
    return copyhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64