算法之复制复杂链表

本文主要是介绍算法之复制复杂链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
为啥这代码写的如此冗余
  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 };
这篇关于算法之复制复杂链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
Java教程

算法之复制复杂链表

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯
