【演算法】如果鏈表里有隨機指標怎么拷貝？-力扣經典題目講解【保姆級別教程】
先贊后看好習慣 打字不容易，這都是很用心做的，希望得到支持你 大家的點贊和支持對于我來說是一種非常重要的動力 看完之后別忘記關注我哦！???
題目：力扣OJ138-復制帶隨即指標的鏈表
本篇建議收藏后食用~
文章目錄
- 題目
- 分析
- 一些關于學資料結構的提醒
- 演算法及實作
- 鏈表結構
- 解題思路
- 完整代碼
- 尾聲
題目
分析
題目初步分析：
看完這道題，我們首先要知道的-什么是帶有隨機指標的鏈表，
當然，題目寫的太“高級”，感覺很厲害的樣子，其實沒那么難理解
我們通過leetcode提供給我們的結構圖，我們可以看到，
這個特殊的鏈表總體結構上是一個單鏈表，與單鏈表不同的是，這個鏈表的每一個結點里多了一個random指標，它指向的結點是不確定的，有可能指向第一個結點，有可能指向第二個，有可能指向它自己，有可能指向NULL，這就給我們的拷貝制造了很多麻煩，
當然，這道題對于初學資料結構的伙伴來說，算是一道比較難的題目了，所以，看完這篇博客，相信我們可以很好地解決這個問題，并且我相信我們的能力，會有一個層次的提升，
一些關于學資料結構的提醒
我曾經在以前的博客里面講過，學習編程，特別是學到指標，資料結構這些內容的時候，畫圖是非常重要的，這些題目，雖然我學習的時間并不是很久，但是我可以很負責任地說，學編程，不畫圖，一定學不好，伙伴們看看這道題，不畫圖根本不可能想得出來，
演算法及實作
鏈表結構
struct Node {
int val;
struct Node *next;
struct Node *random;
};
解題思路
首先：想要解決這一道題，想要直接拷貝是肯定不行的，如果我們拷貝出來的空間不和原來的結點有聯系的話，
random是處理不了的，
所以，我們的新開辟出來的結點一定要和原來的結點有聯系，因此
第一步：將新拷貝的結點鏈接到我們原來的結點的后面，并重新鏈接起來，做完這個步驟，原來三個結點的鏈表會變成六個結點，原來四個結點的鏈表會變成八個結點，
即如圖所示
做完這一步，我們新拷貝的結點就和我們原來的結點建立了聯系，
第二步： 處理
random指標： 做完第一步之后，我們要敏銳地發現，拷貝出來的結點的random所指向的結點，應該是原來結點的random所指向的結點的后面那個結點，這樣我們的random不就可以處理了嗎，
我們再梳理一次上面那句話：新拷貝出來的結點的random指向原來拷貝出來的random所指向的結點的后面那個結點（當然，如果原來random指向的是NULL，那我們新random也直接指向NULL就可以了，這里記得判斷一下
，否則容易造成對空指標解參考的問題，導致OJ過不了，） 這個就是整道題的精髓所在，處理random的方法，
做完第二步之后，我們就處理好了random指標的問題，最麻煩的一步解決了，
第三步：斷開新鏈表和舊鏈表的聯系
目前的狀況是這樣子的：（由于加上random的箭頭，版面太亂了，圖片里就不加上箭頭了，用“已處理好”代替）
現在需要做的，就是斷開二者聯系，使它成為一個獨立鏈表，
首先，我們需要三個指標,防止結點的丟失：cur(用于遍歷)，copy(cur后面拷貝的結點),next(copy后面的那個結點，也就是原鏈表cur后面的那個結點)，
這里只要注意一下拆指標的順序即可，這一部分我們在其它的題也接觸很多了，這里就不贅述了，
完整代碼
struct Node* copyRandomList(struct Node* head) {
if (head == NULL) {//防止傳進來空鏈表
return NULL;
}
struct Node* cur = head;
//1.拷貝鏈表，放到原來結點的后面
while (cur) {
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->next = NULL;
copy->val = cur->val;
copy->next = cur->next;//先讓新的指向后面
cur->next = copy;//然后再讓前面的指向新的
//注意順序
//讓指標動起來(迭代)
cur = cur->next->next;
}
//2.處理random
cur = head;//cur重新來過
while (cur) {
struct Node* copy = cur->next;
//寫鏈表一定要細心再細心
//題目說random有可能為空，所以：
if (cur->random != NULL) {//記得判斷一下
copy->random = cur->random->next;//關鍵
}
else {
copy->random = NULL;
}
//迭代
cur = cur->next->next;//因為中間間隔了一個拷貝結點
}
//3.拆
//這里一定要畫圖分析注意一下
//三個指標，cur copy next，當走到最后一步的時候，next已經是空了，這個時候copy=copy->next->next就不對了，應該直接置成空
//此時我們發現，我們的函式是要回傳新的頭結點的，但是我們弄丟了，所以要保存
cur = head;
struct Node* copyhead = head->next;//先保存頭
while (cur) {
struct Node* copy = cur->next;
struct Node* next = copy->next;
cur->next = next;
if (next != NULL) {//最后一步防止next已經為空了
copy->next = next->next;
}
//迭代
cur = next;
}
return copyhead;
}
尾聲
以上就是這期博客所帶來的-復制帶有隨機指標的鏈表的力扣經典題，這題對于初學者來說難度確實有點高，但是相信看到這里的伙伴，應該已經可以基本完成這道題了，這邊建議下去以后我們再獨立做一遍，如果你感覺這篇博客對你有幫助的話，別忘了點贊關注收藏轉發哦！你們的支持是我必不可少的動力
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/385603.html
標籤：其他
下一篇：配置 PyCharm for Linux 設定啟動圖示 pycharm-edu-2021.3.1 Ubuntu 18.04.6 LTS