LeetCode 复制带随机指针的链表

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

题目大意

　　略。

分析

　　空间复杂度 O(1) 的做法非常开拓思维。

代码如下

 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         // 在原链表中交替嵌入新节点
26         while(p1 != NULL) {
27             Node *t = new Node();
28             
29             t->next = p1->next;
30             t->val = p1->val;
31             p1->next = t;
32             p1 = t->next;
33         }
34         
35         newhead = head->next;
36         p1 = head;
37         p2 = newhead;
38         // 拷贝random
39         while(1) {
40             if(p1->random == NULL) p2->random = NULL;
41             else p2->random = p1->random->next;
42             p1 = p2->next;
43             if(p1 == NULL) break;
44             p2 = p1->next;
45         }
46         
47         p1 = head;
48         p2 = newhead;
49         // 分离
50         while(1) {
51             p1 = p1->next = p2->next;
52             if(p1 == NULL) break;
53             p2 = p2->next = p1->next;
54         }
55         return newhead;
56     }
57 };

View Code