数据结构每日亿题(四)

复制带随机指针的链表

原题传送门：力扣
题目：
这题的大概意思就是：
有这样一个链表，他比普通的链表多一个成员变量：random指针，这个random指针指向的是这个链表中随机一个地方，这个地方是其它节点的位置或者是空指针。现在题目的要求是让你把这个链表复制出来。

一.大概思路

这题的难点主要就是这个随机指针因为这是没有规律的可能这个链表的第一个节点指向第二个节点，但是另一个节点可能指向的就是第三个节点。
虽然这题可以用暴力方法来求解：就是先遍历第一遍找到第一个节点指向的位置在复制时把这个位置写出来，然后在遍历第二遍，第三遍…。这方法可以是可以但是时间复杂度是O(N^2),太多了，可以用但是不推荐。

接下来我来讲一个特别神奇的思路：

第一步

先随便拿个链表做说明，我们在每个节点的后面添加一个新的节点，这个新的节点的里的值和它上个节点的值是一样的：
像这样都连起来了，但是新节点的random还没有设置，接下来就是这个思路的厉害之处。

第二步

先定义两个指针cur,next，我们虽然不知道新节点的random是指向哪里，但是我们直到原来节点的random指向哪里。我们先看第一个原节点的random指向的是NULL，现在我们把这种情况当成一种特殊情况，就是先判断原节点指向的是不是空，是的话新节点的random也指向空。

然后在判断其它情况，这里让cur,next设置好一个新节点的random后往后跳一步：
我们注意看原节点13的random指向的应该是7这个节点，所以说现在我们希望next指向的这个新节点的random也指向新节点的7，但是我们有没有发现我们希望找到的位置就在原来7这个节点的后一步。
用代码来说：

cur->random->next
1

上面这个位置是不是就是我们新节点13的random指向的位置？
像这样next,cur一步一步的往后走，是不是就把新加上去的这些节点的random都配置好了。
这种方法的好处就是不管你之前节点的random指向哪个地方，我新节点都指向你这个地方的下一个位置。

第三步

新节点的random都配置好了，但是我们返回的是一个新链表，所以现在我们要把之前新加的那些节点都取出来合成一个新的链表。取下来也不难，就是将一个指针从头开始遍历。

二.代码实现

第一步

	//在每个节点后面插一个复制的节点
    struct Node* cur = head;
    while(cur)
    {
        struct Node* next = cur->next;
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->val = cur->val;
        cur->next = newnode;
        newnode->next = next;
        cur = next;
    }
1
2
3
4
5
6
7
8
9
10
11

接下来我会将代码分成几部分来讲：

    struct Node* cur = head;
    while(cur)
    {
        struct Node* next = cur->next;
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
1
2
3
4
5

先把前戏做好，定义好三个指针：

这个代码时把新节点的值改成原来一样的值。

newnode->val = cur->val;
1

然后把三个节点链接起来就行。

cur->next = newnode;
newnode->next = next;
1
2

最后cur指向下一个节点继续往后走，这样就把所有的新节点和原来的节点放好了。

cur = next;
1

第二步

    //设置复制的节点的rondom
    cur = head;
    while(cur)
    {   
        struct Node* next = cur->next;
        if(cur->random == NULL)
        {
            next->random = NULL;
        }
        else
        {
            next->random = cur->random->next;
        }
        cur = next->next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我们先将cur指针恢复到原位：

cur = head;
1

然后在看循环里面的内容：

这是一个特殊的判断，如果原节点的random指向空，我们这个新节点的random也指向空。

struct Node* next = cur->next;
if(cur->random == NULL)
{
	next->random = NULL;
}
1
2
3
4
5

再看普通情况：

else
{
	next->random = cur->random->next;
}
1
2
3
4

把新节点的random指向原来节点的random的下一个节点。

最后cur指向下一个位置继续判断

cur = next->next;
1

注意，这个下一个位置是原来链表那些节点的第二个位置：
因为next每次在循环的开始就已经指向了当前cur的next,所以不用在对其进行相关的操作了。

第三步

    //将复制在上面的节点取下来尾插变成新的链表
    cur = head;
    struct Node* nhead = NULL;
    struct Node* tail = NULL;
    while(cur)
    {
        struct Node* next = cur->next;
        struct Node* curnext = next->next;
        if(nhead == NULL)
        {
            nhead = tail = next;
        }
        else
        {
            tail->next = next;
            tail = tail->next;
        }
        cur->next = curnext;
        cur = curnext;
    } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

最后我们就要进行收尾操作：尾插。

先定义两个指针nhead,tail然后再把cur指针复位重新指向链表最开始的位置：

cur = head;
struct Node* nhead = NULL;
struct Node* tail = NULL;
1
2
3

然后在定义两个指针：

struct Node* next = cur->next;
struct Node* curnext = next->next;
1
2

尾插同样要分两种情况，第一种情况就是tail,nhead为空时，也就是刚开始的时候。

if(nhead == NULL)
{
	nhead = tail = next;
}
1
2
3
4

这时候我们让nhead,tail都指向此时next指向的节点：
这里7这个节点原来指向啥还是啥，我们现在看的像是把这个节点拿了下来。

拿下来一个节点之后，我们最后把原来两个节点还原：

cur->next = curnext;
1

然后cur继续往后跳两步：

cur = curnext;
1

curnext和next每次在循环之前就已经指向了该指向的位置。

接下来我们再来看当nhead,tail不是空的情况：
现在我们需要将next指向的节点取下来：

else
{
	tail->next = next;
	tail = tail->next;
}
1
2
3
4
5

这样就把13这个节点取下来了，接下来的操作就是像这样一直循环一直循环，直到cur指针直到空时结束。现在就把最开始建立的那些新节点全部拿下来并且链接在一起了。
现在不用担心random的问题，因为第三步，根本没改变过每个节点里random的内容，所以之前指向哪里，现在还指向哪里。

最后结果：
每个节点random指向的节点我就不画了。现在我们返回nhead就行了。

三.代码

/**
 * 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* newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->val = cur->val;
        cur->next = newnode;
        newnode->next = next;
        cur = next;
    }

    //设置复制的节点的rondom
    cur = head;
    while(cur)
    {   
        struct Node* next = cur->next;
        if(cur->random == NULL)
        {
            next->random = NULL;
        }
        else
        {
            next->random = cur->random->next;
        }
        cur = next->next;
    }

    //将复制在上面的节点取下来尾插变成新的链表
    cur = head;
    struct Node* nhead = NULL;
    struct Node* tail = NULL;
    while(cur)
    {
        struct Node* next = cur->next;
        struct Node* curnext = next->next;
        if(nhead == NULL)
        {
            nhead = tail = next;
        }
        else
        {
            tail->next = next;
            tail = tail->next;
        }
        cur->next = curnext;
        cur = curnext;
    }    
    return nhead;
}
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