Careercup

2014-05-01 01:32

原题：

Given a linked list where apart from the next pointer, every node also has a pointer named random which can point to any other node in the linked list. Make a copy of the linked list.

题目：给定一个单链表，每个链表除了next指针以外，还有一个random指针，随机地指向nullptr或者链表中的某个节点。请设计算法完成一份链表的硬拷贝。

解法：Leetcode上有相关题目，请看题解LeetCode - Copy List with Random Pointer。

代码：

 1 // http://www.careercup.com/question?id=5412018236424192
 2 #include <unordered_map>
 3 using namespace std;
 4 
 5 struct RandomListNode {
 6     int label;
 7     RandomListNode *next, *random;
 8     RandomListNode(int x) : label(x), next(NULL), random(NULL) {};
 9 };
10 
11 class Solution {
12 public:
13     RandomListNode *copyRandomList(RandomListNode *head) {
14         // IMPORTANT: Please reset any member data you declared, as
15         // the same Solution instance will be reused for each test case.
16         int n;
17         
18         if(nullptr == head){
19             return nullptr;
20         }
21         
22         n = 0;
23         RandomListNode *ptr;
24         
25         ptr = head;
26         while(ptr != nullptr){
27             ++n;
28             mri[ptr] = n;
29             ptr = ptr->next;
30         }
31         
32         RandomListNode *root, *tail;
33         ptr = head;
34         
35         int i = 0;
36         tail = root = nullptr;
37         while(ptr != nullptr){
38             ++i;
39             if (root == nullptr) {
40                 root = tail = new RandomListNode(ptr->label);
41             } else {
42                 tail->next = new RandomListNode(ptr->label);
43                 tail = tail->next;
44             }
45             mir[i] = tail;
46             ptr = ptr->next;
47         }
48         
49         RandomListNode *p1, *p2;
50         
51         p1 = head;
52         p2 = root;
53         while(p1 != nullptr){
54             if(p1->random != nullptr){
55                 p2->random = mir[mri[p1->random]];
56             }
57             p1 = p1->next;
58             p2 = p2->next;
59         }
60         
61         mir.clear();
62         mri.clear();
63         
64         return root;
65     }
66 private:
67     unordered_map<RandomListNode *, int> mri;
68     unordered_map<int, RandomListNode *> mir;
69 };