劍指offer-複雜連結串列的複製

WellBay 1月前


標籤:val   div   直接   nod   對映   off   另一個   tail   ima   

描述

輸入一個複雜連結串列(每個節點中有節點值,以及兩個指標,一個指向下一個節點,另一個特殊指標random指向一個隨機節點),請對此連結串列進行深拷貝,並返回拷貝後的頭結點。(注意,輸出結果中請不要返回引數中的節點引用,否則判題程式會直接返回空)。 下圖是一個含有5個結點的複雜連結串列。圖中實線箭頭表示next指標,虛線箭頭表示random指標。為簡單起見,指向null的指標沒有畫出。

 

 

求解思路:

  1. 第一個迴圈先構建非隨機鏈(即只考慮next指標),並用map記錄label與新連結串列各節點的對映
  2. 第二個迴圈根據map,完善隨機指標。

程式碼:

 

 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 public:
12     RandomListNode* Clone(RandomListNode* pHead) {
13         //  如果把複雜連結串列看作隨機鏈和非隨機鏈,那先確定非隨機鏈
14         // 然後依次檢驗每個節點的隨機指標,讀取val,通過val確定新鏈的隨機指標
15         // 改進:在構建非隨機連結串列時,新建map對映 val和random(這裡記錄節點)
16         std::map<int,RandomListNode*> lm;
17         RandomListNode* newHead=NULL;
18         RandomListNode* tail;   // 記錄尾節點
19         // 完成非隨機連結串列的構建
20         RandomListNode* ergNode=pHead;
21         while(ergNode!=nullptr){
22             RandomListNode* rn=new RandomListNode(ergNode->label);
23             if(newHead==nullptr){
24                 newHead=rn;
25             }else{
26                 tail->next=rn;
27             }
28             tail=rn;
29             // 構建label和node的對映
30             // lm.insert(pair<int,RandomListNode*>(rn->label,rn));
31             lm[rn->label]=rn;
32             ergNode=ergNode->next;
33         }
34         // 再用一個迴圈完成隨機連結串列的構建
35         ergNode=pHead;  // 遍歷原有連結串列
36         RandomListNode* repNode=newHead;  // 補充現有連結串列
37         while(ergNode!=nullptr){
38             if(ergNode->random!=nullptr){
39                 repNode->random=lm[ergNode->random->label];
40                 int f=1;
41             }
42             ergNode=ergNode->next;
43             repNode=repNode->next;
44         }
45         return newHead;
46     }
47 };

 

 

 

劍指offer-複雜連結串列的複製

標籤:val   div   直接   nod   對映   off   另一個   tail   ima   

原文地址:https://www.cnblogs.com/zgll/p/15072949.html


上一篇:Bootstrap元件2
下一篇:幾種瀏覽器