剑指Offer - 九度1524 - 复杂链表的复制

剑指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的目的在于学会,而不是通过。
剑指Offer - 九度1524 - 复杂链表的复制
  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 */
剑指Offer - 九度1524 - 复杂链表的复制

剑指Offer - 九度1524 - 复杂链表的复制

上一篇:Unique Paths II


下一篇:Memcached 深度分析