为啥这代码写的如此冗余
1 /*
2 struct RandomListNode {
3 int label;
4 struct RandomListNode *next, *random;
5 RandomListNode(int x) :
6 label(x), next(NULL), random(NULL) {
7 }
8 };
9 */
10 #if 0
11 // Clone.cpp : 定义控制台应用程序的入口点。
12 //
13
14 #include "stdafx.h"
15 #include "iostream"
16 using namespace std;
17
18
19
20 #if 0
21
22 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。
23 （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
24
25 #endif
26
27
28 //解题思路：
29
30 //遍历链表
31 //创建拷贝的链表
32 //给它赋同样的值
33 //难点在于那个随机指针
34 //可以通过偏移进行计算得出
35 //todo 青春怎么过 都觉得奢侈。。。。。。
36
37
38
39 struct RandomListNode {
40 int label;
41 struct RandomListNode *next, *random;
42 RandomListNode(int x) :
43 label(x), next(NULL), random(NULL) {
44 }
45 };
46
47 class Solution {
48 public:
49 RandomListNode* Clone(RandomListNode* pHead)
50 {//1
51 if (pHead == NULL)
52 {
53 return NULL;
54 }
55
56 RandomListNode* pBack = pHead;
57 RandomListNode* pClone;
58
59 pClone = (RandomListNode*)malloc(sizeof(RandomListNode));
60 pClone->label = pHead->label;
61 pClone->next = NULL;
62 pBack = pBack->next;
63 RandomListNode* pClone_next = pClone;
64 /*复制链表*/
65 while (pBack != NULL)
66 {
67 RandomListNode* pTemp;
68 pTemp = (RandomListNode*)malloc(sizeof(RandomListNode));
69 if (pTemp == NULL)
70 {
71 return NULL;
72 }
73
74 pTemp->label = pBack->label;
75 pTemp->next = NULL;
76 pClone_next->next = pTemp;
77 pClone_next = pClone_next->next;
78 pBack = pBack->next;
79 }
80 /*复制链表*/
81 /*准备复制随机指针*/
82
83 RandomListNode* pTemp = pClone;//pTemp用于对每个节点进行遍历。pTemp其实指向头结点
84 RandomListNode* pTempRun = pClone;//pTempRun相当于pHead的临时变量，用于“运营”。其实指向头结点
85 // pHead = pHead->next;
86 RandomListNode* pCountRandom = pHead;//pCountRandom用于对随机指针的遍历
87 RandomListNode* pHeadRun = pHead;//我不知道这些变量的定义是什么。从下文来看，这个是跟ptemp的指针意义相同
88 int count = 0;
89 while (pTemp != NULL)//
90 {
91 if (pHeadRun->random != NULL)
92 {
93 while ( pHeadRun->random != pCountRandom )//这样写 是不考虑随机指针指向自身
94 {
95 count++;
96 if (pCountRandom == NULL)
97 {
98 pCountRandom = pHead;
99 }
100 else
101 {
102 pCountRandom = pCountRandom->next;
103 }
104
105 }
106 //一直遍历，直至找到pHeadRun的随机指针为止，同时，用count记录遍历了多少次
107
108 for (int i = 0; i <count; i++)
109 {
110 pTempRun = pTempRun->next;//
111 }
112 count = 0;
113 pTemp->random = pTempRun;//找到后进行复制
114 // printf("%x\r\n", pHead);
115 // printf("%x\r\n", pHead->random);
116 //int offerset = pHead->random - pHead;
117 // pTemp->random = pTemp + offerset;
118 }
119 else
120 {
121 count = 0;
122 pTemp->random=NULL;
123 }
124 pCountRandom = pHead;//pCountRandom 进行复位
125 pHeadRun = pHeadRun->next;//开始处理下一个节点
126
127 pTemp = pTemp->next;
128
129 pTempRun = pClone;
130 }
131
132 return pClone;
133
134
135 }//1
136 /*--复制随机指针*/
137 //这代码读起来来啥感觉，可读性极差，非常繁琐
138 };
139 int main()
140 {
141 Solution solution;
142 RandomListNode* pHead = NULL;
143 pHead = (RandomListNode*)malloc(sizeof(RandomListNode));
144 pHead->label = 1;
145 pHead->next = NULL;
146 RandomListNode* q = pHead;
147 int i = 0;
148 while (i < 4)
149 {
150 RandomListNode* pTemp = NULL;
151 //
152 pTemp = (RandomListNode*)malloc(sizeof(RandomListNode));
153 pTemp->label =i+2;
154 pTemp->next = NULL;
155 q->next = pTemp;
156 q = q->next;
157 i++;
158
159 //pHead = pHead->next->next;
160 // pHeadNext = pHeadNext->next;
161 }
162 char* trp = "112";
163 trp[1];
164 //pHead->random = pHead[2];
165 q = pHead;
166 RandomListNode* q1 = q;
167 q = q->next;
168 RandomListNode* q2 = q;
169 q = q->next;
170 RandomListNode* q3 = q;
171 q = q->next;
172 RandomListNode* q4 = q;
173 q = q->next;
174 RandomListNode* q5 = q;
175
176
177 q1->random = q3;
178 q2->random = q5;
179 q3->random = NULL;
180 q4->random = q2;
181 q5->random = NULL;
182
183 solution.Clone(pHead);
184 return 0;
185 }
186
187
188 #endif
189 class Solution {
190 public:
191 RandomListNode* Clone(RandomListNode* pHead)
192 {//1
193 if (pHead == NULL)
194 {
195 return NULL;
196 }
197
198 RandomListNode* pBack = pHead;
199 RandomListNode* pClone;
200
201 pClone = (RandomListNode*)malloc(sizeof(RandomListNode));
202 pClone->label = pHead->label;
203 pClone->next = NULL;
204 pBack = pBack->next;
205 RandomListNode* pClone_next = pClone;
206 /*复制链表*/
207 while (pBack != NULL)
208 {
209 RandomListNode* pTemp;
210 pTemp = (RandomListNode*)malloc(sizeof(RandomListNode));
211 if (pTemp == NULL)
212 {
213 return NULL;
214 }
215
216 pTemp->label = pBack->label;
217 pTemp->next = NULL;
218 pClone_next->next = pTemp;
219 pClone_next = pClone_next->next;
220 pBack = pBack->next;
221 }
222 /*复制链表*/
223 /*准备复制随机指针*/
224
225 RandomListNode* pTemp = pClone;//pTemp用于对每个节点进行遍历。pTemp其实指向头结点
226 RandomListNode* pTempRun = pClone;//pTempRun相当于pHead的临时变量，用于“运营”。其实指向头结点
227 // pHead = pHead->next;
228 RandomListNode* pCountRandom = pHead;//pCountRandom用于对随机指针的遍历
229 RandomListNode* pHeadRun = pHead;//我不知道这些变量的定义是什么。从下文来看，这个是跟ptemp的指针意义相同---两者意义不同哈，一个是原链表的地址，一个是赋值
230 int count = 0;
231 while (pTemp != NULL)//
232 {
233 if (pHeadRun->random != NULL)
234 {
235 while ( pHeadRun->random != pCountRandom )//这样写 是不考虑随机指针指向自身
236 {
237 count++;
238 if (pCountRandom == NULL)
239 {
240 pCountRandom = pHead;//如果到了末尾还没有找到，那再从头开始找
241 }
242 else
243 {
244 pCountRandom = pCountRandom->next;
245 }
246
247 }
248 //一直遍历，直至找到pHeadRun的随机指针为止，同时，用count记录遍历了多少次
249 // if (pCountRandom == NULL)
250 // {
251 // pTemp->random=NULL;
252 // }
253 // else
254
255 // pTemp->random=pCountRandom;//不能这样做，不能利用原指针的地址
256 // count = 0;
257 #if 1
258 for (int i = 0; i <count; i++)
259 {
260 pTempRun = pTempRun->next;//
261 }
262 count = 0;
263 pTemp->random = pTempRun;//找到后进行赋值
264 #endif
265
266 }
267 else
268 {
269 count = 0;
270 pTemp->random=NULL;
271 }
272 pCountRandom = pHead;//pCountRandom 进行复位
273 pHeadRun = pHeadRun->next;
274
275 pTemp = pTemp->next;//开始处理下一个节点
276
277 pTempRun = pClone;
278 }
279
280 return pClone;
281
282
283 }//1
284 /*--复制随机指针*/
285 //这代码读起来来啥感觉，可读性极差，非常繁琐,看起来非常难受
286 };