LeetCode 复制带随机指针的链表

题目链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

题目大意

分析

代码如下

 1 /*
 2 // Definition for a Node.
 3 class Node {
 4 public:
 5     int val;
 6     Node* next;
 7     Node* random;
 8 
 9     Node() {}
10 
11     Node(int _val, Node* _next, Node* _random) {
12         val = _val;
13         next = _next;
14         random = _random;
15     }
16 };
17 */
18 class Solution {
19 public:
20     Node* copyRandomList(Node* head) {
21         if(head == NULL) return NULL;
22         
23         Node *p1 = head, *p2, *newhead;
24         
25         if(p1->next == NULL) {
26             p1 = new Node();
27             p1->val = head->val;
28             p1->next = NULL;
29             if(head->random == NULL) p1->random = NULL;
30             else p1->random = p1;
31             
32             return p1;
33         }
34         
35         // 在原链表中交替嵌入新节点
36         while(p1 != NULL) {
37             Node *t = new Node();
38             
39             t->next = p1->next;
40             t->val = p1->val;
41             p1->next = t;
42             p1 = t->next;
43         }
44         
45         newhead = head->next;
46         p1 = head;
47         p2 = newhead;
48         // 拷贝random
49         while(1) {
50             if(p1->random == NULL) p2->random = NULL;
51             else p2->random = p1->random->next;
52             p1 = p2->next;
53             if(p1 == NULL) break;
54             p2 = p1->next;
55         }
56         
57         p1 = head;
58         p2 = newhead;
59         // 分离
60         while(1) {
61             p1 = p1->next = p2->next;
62             if(p1 == NULL) break;
63             p2 = p2->next = p1->next;
64         }
65         return newhead;
66     }
67 };