A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
这题貌似见过，大概是编程之美之类吧。
复习一下深拷贝和浅拷贝的区别：
深拷贝保存了指针指向的内容，二浅拷贝应对指针指示给指针赋值。
所以对于有指针的地方，浅拷贝非常不安全。
这段代码用了2个栈，感觉很不效率，空间O(n)。
有个空间O（1）的。
|
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 |
/** * Definition for singly-linked list with a random pointer. * struct RandomListNode { * int label; * RandomListNode *next, *random; * RandomListNode(int x) : label(x), next(NULL), random(NULL) {} * }; */class
Solution {public: RandomListNode *copyRandomList(RandomListNode *head) { stack<RandomListNode *> sk; stack<RandomListNode *> sk2; if(head == NULL)return
NULL; RandomListNode *temp = head; RandomListNode *cp = new
RandomListNode (0); RandomListNode *cpp = cp; while(temp != NULL) { int
val = temp->label; RandomListNode* node = new
RandomListNode(val); cpp->next = node; cpp = node; sk.push(temp); temp = temp ->next; sk.top()->next = cpp; } while(! sk.empty()) { temp =sk.top(); if(temp->random != NULL) temp->next->random = temp->random->next; sk2.push(temp); sk.pop(); } while(! sk2.empty()) { temp = sk2.top(); sk2.pop(); if(sk2.empty())temp->next =NULL; else { temp->next =sk2.top(); } } return
cp->next; }}; |
Copy List with Random Pointer,布布扣,bubuko.com
原文：http://www.cnblogs.com/pengyu2003/p/3626836.html