剑指Offer - 九度1524 - 复杂链表的复制
2014-02-07 01:30
- 题目描述：
-
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。
- 输入：
-
输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行为一个整数n (1<=n<=1000)：n代表将要输入的链表元素的个数。（节点编号从1开始）。
接下来有n个数，表示链表节点中的值。
接下来有n个数Ti，Ti表示第i个节点的另一个指针指向。
Ti = 0 表示这个指针为NULL。
- 输出：
-
对应每个测试案例，
输出n行，每行有二个数，第一个代表当前节点值，第二个代表当前节点的特殊指针的值。
- 样例输入：
-
5 1 2 3 4 5 3 5 0 2 0
- 样例输出：
-
1 3 2 5 3 0 4 2 5 0
题意分析：
对于一个含有n个节点的单向链表，指针域中除了next之外，还有一个指向另一个节点或者指向NULL的随机指针。本题的任务是复制一份这样的链表出来。
我的思路，当然是先给节点编号，然后根据编号对应关系重建链表。
其中重要的一步，就是将这些链表节点和1~n的n个整数一一映射起来。这样一来，就能方便地表示随机指针中到底是谁指向谁了。
因为使用了map，所以映射的过程时间复杂度为O(n * log(n))。复制新链表时，也需要查反向映射，仍需要O(n * log(n))的时间。
如果使用适当的hash策略，可以做到接近O(1)的映射时间，时间复杂度也可以降到O(n)，但需要额外编码就是了。空间复杂度为O(n)。
最后，不要偷懒直接用数组AC掉(^_^)，AC的目的在于学会，而不是通过。
1 // 688806 zhuli19901106 1524 Accepted 点击此处查看所有case的执行结果 1160KB 3820B 50MS 2 // 201402012144 3 #include <cstdio> 4 #include <map> 5 using namespace std; 6 7 struct RandomListNode { 8 int label; 9 RandomListNode *next, *random; 10 RandomListNode(int x) : label(x), next(NULL), random(NULL) {} 11 }; 12 13 // This code segment is copied from my leetcode problem set. 14 class Solution { 15 public: 16 RandomListNode *copyRandomList(RandomListNode *head) { 17 int n; 18 19 if(NULL == head){ 20 return NULL; 21 } 22 23 n = 0; 24 RandomListNode *ptr; 25 26 mri.clear(); 27 mir.clear(); 28 29 ptr = head; 30 while(ptr != NULL){ 31 ++n; 32 mri[ptr] = n; 33 ptr = ptr->next; 34 } 35 36 RandomListNode *root = new RandomListNode(0), *tail; 37 ptr = head; 38 int i = 0; 39 tail = root; 40 while(ptr != NULL){ 41 ++i; 42 tail->next = new RandomListNode(ptr->label); 43 tail = tail->next; 44 mir[i] = tail; 45 ptr = ptr->next; 46 } 47 48 RandomListNode *p1, *p2; 49 50 p1 = head; 51 p2 = root->next; 52 while(p1 != NULL){ 53 if(p1->random != NULL){ 54 p2->random = mir[mri[p1->random]]; 55 } 56 p1 = p1->next; 57 p2 = p2->next; 58 } 59 60 head = root->next; 61 delete root; 62 mir.clear(); 63 mri.clear(); 64 65 return head; 66 } 67 68 RandomListNode *deleteList(RandomListNode *head) { 69 RandomListNode *ptr1, *ptr2; 70 71 if (NULL == head) { 72 return NULL; 73 } 74 75 ptr1 = head; 76 while (ptr1 != NULL) { 77 ptr2 = ptr1->next; 78 delete ptr1; 79 ptr1 = ptr2; 80 } 81 82 return NULL; 83 } 84 private: 85 map<RandomListNode *, int> mri; 86 map<int, RandomListNode *> mir; 87 }; 88 89 int main() 90 { 91 map<RandomListNode *, int> mri; 92 map<int, RandomListNode *> mir; 93 int n, i; 94 int label; 95 RandomListNode *head1, *head2, *tail, *ptr; 96 Solution solution; 97 98 while (scanf("%d", &n) == 1) { 99 mri.clear(); 100 mir.clear(); 101 head1 = head2 = tail = NULL; 102 for (i = 1; i <= n; ++i) { 103 scanf("%d", &label); 104 if (tail == NULL) { 105 head1 = tail = new RandomListNode(label); 106 } else { 107 tail->next = new RandomListNode(label); 108 tail = tail->next; 109 } 110 mri[tail] = i; 111 mir[i] = tail; 112 } 113 114 for (i = 1; i <= n; ++i) { 115 scanf("%d", &label); 116 if (label > 0) { 117 ptr = mir[i]; 118 ptr->random = mir[label]; 119 } 120 } 121 122 head2 = solution.copyRandomList(head1); 123 ptr = head2; 124 while (ptr != NULL) { 125 printf("%d ", ptr->label); 126 if (ptr->random != NULL) { 127 printf("%d\n", ptr->random->label); 128 } else { 129 printf("0\n"); 130 } 131 ptr = ptr->next; 132 } 133 134 head1 = solution.deleteList(head1); 135 head2 = solution.deleteList(head2); 136 } 137 138 return 0; 139 } 140 /* 141 // 688773 zhuli19901106 1524 Accepted 点击此处查看所有case的执行结果 1024KB 544B 40MS 142 // 201402012022 143 #include <cstdio> 144 #include <vector> 145 using namespace std; 146 147 int main() 148 { 149 vector<int> va, vb; 150 int n, i; 151 int a, b; 152 153 while (scanf("%d", &n) == 1) { 154 va.clear(); 155 vb.clear(); 156 va.push_back(0); 157 vb.push_back(0); 158 for (i = 1; i <= n; ++i) { 159 scanf("%d", &a); 160 va.push_back(a); 161 } 162 for (i = 1; i <= n; ++i) { 163 scanf("%d", &b); 164 vb.push_back(b); 165 } 166 for (i = 1; i <= n; ++i) { 167 printf("%d %d\n", va[i], va[vb[i]]); 168 } 169 } 170 171 return 0; 172 } 173 */