超详细-Leetcode题解138.复制带随机指针的链表_138. 复制带随机指针的链表 什么意思

生命不息，奋斗不止；保持热爱，奔赴山河。

138.复制带随机指针的链表

Leetcode链接：复制带随机指针的链表

总的代码在文章末。
大家看到这题有什么想法吗？题目的意思是让我们完完全全在弄一个一模一样的链表，咋弄？
我们可能会想到用一个cur指针从原链表初始位置开始，进行遍历，用copy指针指向一个新链表，将cur的val给copy，但这里的random咋办？怎么找到copy的random，遍历一遍，通过val值找，但要是有两个的val值是一样的咋整？就算val都不一样，但这一个个遍历效率不高，时间复杂度是 O（N*2）,这里介绍一种用C语言写的，不借助任何容器的方法。

具体步骤：

代码部分：

struct Node* copyRandomList(struct Node* head) {
    //1.copy节点链接在原节点的后面
	 struct Node* cur = head;
     while(cur)
     {
         struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
         copy->val = cur->val;

         copy->next = cur->next;
         cur->next = copy;

         cur = copy->next;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

代码部分：

     //2.找copy的random,copy->random = cur->random->next
     cur = head;
     while(cur)
     {
         struct Node* copy = cur->next;
         //这里copy的random指向空需单独考虑
         if(cur->random == NULL)
         {
             copy->random = NULL;
         }
         else
         {
             copy->random = cur->random->next;
         }
         cur = copy->next;
     }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

代码部分：

 //3.拷贝的节点解下来，链接到一起，恢复原链表
     cur = head;
     struct Node* copyHead = NULL;
     struct Node* 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;
         }

         //copyTail不用置空，因为拷贝的节点的最后一个节点的next就是指向空的

         cur->next = 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

总的代码：

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

struct Node* copyRandomList(struct Node* head) {
    //1.copy节点链接在原节点的后面
	 struct Node* cur = head;
     while(cur)
     {
         struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
         copy->val = cur->val;

         copy->next = cur->next;
         cur->next = copy;

         cur = copy->next;
     }

     //2.找copy的random,copy->random = cur->random->next
     cur = head;
     while(cur)
     {
         struct Node* copy = cur->next;
         //这里copy的random指向空需单独考虑
         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(copyTail == NULL)
         {
             copyHead = copyTail = copy;
         }
         else
         {
             copyTail->next = copy;
             copyTail = copyTail->next;
         }

         //copyTail不用置空，因为拷贝的节点的最后一个节点的next就是指向空的

         cur->next = 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

看到这大家发现没，这里难的是思路，代码都是之前链表的插入删除等一些基本操作。

如果对您有所帮助，期待您的点赞和关注呀