🔥個人主頁：@草莓熊Lotso

🎬作者簡介：C++研發方向學習者

📖個人專欄：?《C語言》?《數據結構與算法》《C語言刷題集》《Leetcode刷題指南》

??人生格言：生活是默默的堅持，毅力是永久的享受。??

前言：?隨著編程相關知識點的學習，我們LeetCode的刷題也不能落下。在前面我們也接觸到了洛谷和牛客這兩個刷題網站，但是博主一直都在推薦大家使用力扣，是因為力扣的判題嚴謹且大部分都是接口型題目，與面試中的筆試題也更加貼合。那么還是老樣子，博主會為大家提供我自己的思路和代碼，但是算法題的解法肯定不止一個，歡迎大家一起交流和討論。

---

目錄

鏈表的隨機復制

解題過程：

代碼演示：

---

鏈表的隨機復制

題目鏈接：138. 隨機鏈表的復制 - 力扣（LeetCode）

題目描述：?

題目示例：?

思路：在原鏈表基礎上拷貝節點，置random指針，斷開新舊鏈表

解題過程：

1.我們首先需要了解一下什么是淺拷貝什么是深拷貝

淺拷貝（Shallow Copy）：

? 定義：僅復制變量本身的值，對于指針類型的成員，只復制指針的地址，而不復制指針所指向的內存內容。

? 特點：

? 拷貝后，原變量和新變量中的指針指向同一塊內存空間。

? 實現簡單，通常通過直接賦值（如=運算符）或memcpy等函數完成。

? 風險：當其中一個指針釋放內存后，另一個指針會變成野指針，再次操作可能導致內存錯誤（如重復釋放、訪問已釋放內存）。

深拷貝（Deep Copy）：

? 定義：不僅復制變量本身的值，對于指針類型的成員，會先為新變量的指針分配新的內存空間，再將原指針指向的內容復制到新內存中。

? 特點：

? 拷貝后，原變量和新變量中的指針指向各自獨立的內存空間，兩者互不影響。

? 需要手動實現，通常通過自定義函數完成（需顯式分配內存并復制內容）。

? 安全性高，避免了淺拷貝的內存沖突問題，但實現相對復雜，且會額外消耗內存。

2. 在原鏈表的基礎上拷貝節點

3.置random指針?

一定要記住：copy->random=pcur->random->next

4.斷開新舊鏈表?

時間復雜度：O(N)

代碼演示：

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
typedef struct Node Node;
Node* BuyNode(int x)
{Node*newnode=(Node*)malloc(sizeof(Node));newnode->val=x;newnode->next=newnode->random=NULL;return newnode;
}
void InsertaList(Node*head)
{Node*pcur=head;while(pcur){Node*newnode=BuyNode(pcur->val);Node*next=pcur->next;pcur->next=newnode;newnode->next=next;pcur=next;}
}
void SetRandom(Node*head)
{Node*pcur=head;while(pcur){Node*copy=pcur->next;if(pcur->random)copy->random=pcur->random->next;pcur=copy->next;}
}
struct Node* copyRandomList(struct Node* head) {if(head==NULL){return head;}//拷貝原鏈表的節點并插入原鏈表中InsertaList(head);//設置randomSetRandom(head);//斷開新的鏈表Node*pcur=head;Node*copyhead,*copytail;copyhead=copytail=pcur->next;while(copytail->next){pcur=copytail->next;copytail->next=pcur->next;copytail=copytail->next;}return copyhead;
}

?

這里需要特別注意一下，如果為空特殊處理，不然運行會有問題

---

往期回顧：?

【數據結構初階】--雙向鏈表(一)

【數據結構初階】--雙向鏈表(二)

結語：本篇文章就到此結束了，《LetetCode刷題指南》中的題目比起之間的C語言刷題集中的題目，肯定會更加復雜一些。而且題目形式也不一樣，大家需要注意一下。如果文章對你有幫助的話，歡迎評論，點贊，收藏加關注，感謝大家的支持