复制带随机指针的链表

---

1.思路分析

思路一
首先我们拿到这个题，大思路肯定是先遍历一遍链表

接下来问题来了怎么处理随机指针
最容易想到的肯定是记住随机指针指向的节点与原节点的相对位置

创建一个cur指针从原节点开始遍历找到与原节点random指向的地址相同的节点，并记录相对距离k，这样就好了
但是这种方法的时间复杂度显然为o(n²)
所以我们选择换一种思路

---

思路二
我们可以在节点后面接一个我们新节点，但是新节点实际上是复制原节点的

这样带来的优点是什么？

很显然就是我们可以轻松的找得到random

分两种情况
第一种情况
random指向的是空指针，那么我们复制节点的random就可以直接赋值NULL；
第二种情况
random指向的非空，那么我们该怎么赋值呢？

copy->random=cur->random->next

最后我们在拆开就好啦
这样就赋值成功啦,最重要的是时间复杂度仅仅o(n)

---

2.代码实现

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;
    }
    //拷贝random
    cur=head;
    while(cur)
    {
        struct Node*copy=cur->next;
        
        if(cur->random==NULL)
        {
            copy->random=NULL;

        }
        else
        {
            copy->random=cur->random->next;
        }
        cur=cur->next->next;
    }
    //拆开并链接拷贝节点，恢复原链表
    cur=head;
    struct Node*copyhead=NULL,*copytail=NULL;
    while(cur)
    {
       struct Node*copy=cur->next;
       struct Node*next=copy->next;
       //恢复原链表
       cur->next=next;
       //链接拷贝节点
       if(copytail==NULL)
       {
           copyhead=copytail=copy;
       }
       else
       {
           copytail->next=copy;
           copytail=copytail->next;
       }
       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

3.总结

一道链表经典题，出自剑指offer，反复品味之后对链表的熟悉更进一步