C語言復(fù)雜鏈表的復(fù)制實例詳解
一、題目描述
請實現(xiàn) copyRandomList 函數(shù),復(fù)制一個復(fù)雜鏈表。在復(fù)雜鏈表中,每個節(jié)點(diǎn)除了有一個 next 指針指向下一個節(jié)點(diǎn),還有一個 random 指針指向鏈表中的任意節(jié)點(diǎn)或者 null。
示例1:
輸入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例2:
輸入:head = [[1,1],[2,1]]
輸出:[[1,1],[2,1]]
示例3:
輸入:head = [[3,null],[3,0],[3,null]]
輸出:[[3,null],[3,0],[3,null]]
示例4:
輸入:head = []
輸出:[]
解釋:給定的鏈表為空(空指針),因此返回 null。
提示:
-10000 <= Node.val <= 10000
Node.random 為空(null)或指向鏈表中的節(jié)點(diǎn)。
節(jié)點(diǎn)數(shù)目不超過 1000 。
二、思路分析
注:思路分析中的一些內(nèi)容和圖片參考自力扣各位前輩的題解,感謝他們的無私奉獻(xiàn)
分析
復(fù)制普通鏈表:給定鏈表的頭結(jié)點(diǎn)head,復(fù)制普通鏈表很簡單,只需遍歷鏈表,每輪需要:建立新結(jié)點(diǎn) + 讓前驅(qū)結(jié)點(diǎn)的next指向當(dāng)前這個新結(jié)點(diǎn) + 讓當(dāng)前這個新結(jié)點(diǎn)的next指向空
復(fù)制復(fù)雜鏈表:本題鏈表的結(jié)點(diǎn)新增了 random 指針,指向鏈表中的任意結(jié)點(diǎn)或者null。這個 random 指針意味著在復(fù)制過程中,除了構(gòu)建前驅(qū)結(jié)點(diǎn)的next指針,還要構(gòu)建前驅(qū)結(jié)點(diǎn)的ramdom指針。因此,每輪需要:建立2個新結(jié)點(diǎn) + 讓前驅(qū)結(jié)點(diǎn)的next指向第1個新結(jié)點(diǎn) + 讓前驅(qū)結(jié)點(diǎn)的random指向第2個新結(jié)點(diǎn)。但是這有一個問題:并不是每次都需要建立2個新結(jié)點(diǎn)。有時候前驅(qū)結(jié)點(diǎn)的random指向的是已經(jīng)存在的結(jié)點(diǎn),但是如何判斷出來呢?如果把所有結(jié)點(diǎn)遍歷一遍,那就太麻煩了。
思路
利用哈希表的查詢特點(diǎn),考慮構(gòu)建原鏈表結(jié)點(diǎn)和新鏈表對應(yīng)結(jié)點(diǎn)的鍵值對映射關(guān)系,再遍歷構(gòu)建新鏈表各結(jié)點(diǎn)的next和random引用指向即可。
算法流程:
①若頭節(jié)點(diǎn)head
為空結(jié)點(diǎn),直接返回NULL
;
②初始化:聲明一個哈希表dic
,定義一個結(jié)點(diǎn)cur
指向頭結(jié)點(diǎn),這個cur
控制后面的循環(huán)
③建立哈希映射:遍歷這個鏈表,每個鏈表結(jié)點(diǎn)對應(yīng)建立一個新結(jié)點(diǎn),并向dic
添加鍵值對(原cur結(jié)點(diǎn), 新cur結(jié)點(diǎn))
④構(gòu)建新鏈表的引用指向:構(gòu)建新結(jié)點(diǎn)的next
和random
引用指向
⑤返回值: 返回新鏈表的頭結(jié)點(diǎn),即dic[cur]
三、整體代碼
/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { //若是空鏈表,則返回NULL if(head == NULL) return NULL; //創(chuàng)建一個結(jié)點(diǎn),指向這個鏈表的頭結(jié)點(diǎn)。這個結(jié)點(diǎn)用來控制后面的循環(huán) Node* cur = head; //創(chuàng)建一個哈希表 unordered_map<Node*, Node*> map; while(cur != NULL){ //為鏈表每個結(jié)點(diǎn)創(chuàng)建一個對應(yīng)的新結(jié)點(diǎn),并建立原結(jié)點(diǎn)和新結(jié)點(diǎn)的Map映射 map[cur] = new Node(cur->val); cur = cur->next; } cur = head; //為新鏈表每個結(jié)點(diǎn)的next和random設(shè)置對應(yīng)的指向 while(cur != NULL){ map[cur]->next = map[cur->next]; map[cur]->random = map[cur->random]; cur = cur->next; } //返回新鏈表的頭結(jié)點(diǎn) return map[head]; } };
總結(jié)
本篇文章就到這里了,希望能夠給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
基于Matlab實現(xiàn)數(shù)字音頻分析處理系統(tǒng)
這篇文章主要為大家介紹了如何利用Matlab制作一個帶GUI的數(shù)字音頻分析與處理系統(tǒng)。文中的示例代碼講解詳細(xì),感興趣的小伙伴可以學(xué)習(xí)一下2022-02-02