[劍指Offer] 25.復雜鏈表的復制

 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 class Solution
11 {
12 public:
13     //在舊鏈表中創建新鏈表，此時不處理新鏈表的兄弟結點
14     void CloneNode(RandomListNode* pHead)
15     {
16         RandomListNode* pNode = pHead;
17         while(pNode != NULL)
18         {
19             RandomListNode* newNode = new RandomListNode(pNode->label);
20             newNode->next = pNode->next;
21 
22             pNode->next = newNode;
23             pNode = newNode->next;
24         }
25     }
26     //根據舊鏈表的random結點，初始化新鏈表的random結點
27     void CloneRandomNode(RandomListNode* pHead)
28     {
29         RandomListNode* pNode = pHead;
30         while(pNode != NULL)
31         {
32             RandomListNode* pNewNode = pNode->next;
33             if(pNode->random != NULL)
34                 pNewNode->random = pNode->random->next;
35             pNode = pNewNode->next;
36         }
37     }
38     //從舊鏈表中拆分得到新鏈表
39     RandomListNode* getNewList(RandomListNode* pHead)
40     {
41         RandomListNode* pNode = pHead;
42         RandomListNode* pClonedHead = pHead->next;
43         RandomListNode* pClonedNode = pHead->next;
44         
45         pNode->next = pClonedNode->next;
46         pNode = pNode->next;
47 
48         //循環
49         while(pNode!=NULL)
50         {
51             pClonedNode->next = pNode->next;
52             pClonedNode = pClonedNode->next; 
53             pNode->next = pClonedNode->next; 
54             pNode = pNode->next;
55         }
56         return pClonedHead;
57     }
58     RandomListNode* Clone(RandomListNode* pHead)
59     {
60         if(pHead==NULL) return NULL;
61         CloneNode(pHead);
62         CloneRandomNode(pHead);
63         return getNewList(pHead);
64     }
65 };

轉載于:https://www.cnblogs.com/lca1826/p/6496690.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/456313.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/456313.shtml
英文地址，請注明出處：http://en.pswp.cn/news/456313.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！