【Leedcode】數(shù)據(jù)結(jié)構(gòu)中鏈表必備的面試題（第五期）

---

---

1.題目

138. 復(fù)制帶隨機(jī)指針的鏈表： 如下（示例）：

給你一個長度為n的鏈表，每個節(jié)點(diǎn)包含一個額外增加的隨機(jī)指針random，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。構(gòu)造這個鏈表的深拷貝。深拷貝應(yīng)該正好由n個全新節(jié)點(diǎn)組成，其中每個新節(jié)點(diǎn)的值都設(shè)為其對應(yīng)的原節(jié)點(diǎn)的值。
新節(jié)點(diǎn)的next指針和random指針也都應(yīng)指向復(fù)制鏈表中的新節(jié)點(diǎn)，并使原鏈表和復(fù)制鏈表中的這些指針能夠表示相同的鏈表狀態(tài)。
復(fù)制鏈表中的指針都不應(yīng)指向原鏈表中的節(jié)點(diǎn) 。  返回復(fù)制鏈表的頭節(jié)點(diǎn)。

簡單來說：復(fù)制原來的鏈表（新的），返回新鏈表的頭結(jié)點(diǎn)

---

---

---

2.思路+圖解

（1）第一步：復(fù)制每一個結(jié)點(diǎn)，插入到原結(jié)點(diǎn)和下一個結(jié)點(diǎn)之間

---

第一步代碼實(shí)現(xiàn) ： 如下（示例）：

//1.第一步：先把原來的拷貝一份struct Node* cur = head;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy -> next = cur -> next;cur -> next = copy;copy -> val = cur -> val;cur = copy -> next;}

---

（2）第二步：根據(jù)原結(jié)點(diǎn)random，處理復(fù)制結(jié)點(diǎn)的random

這里要注意：復(fù)制完之后的random所指向的是復(fù)制之前random的next，具體如下圖！

---

---

---

第二步代碼實(shí)現(xiàn) ： 如下（示例）：

// 2.第二步：把random拷貝過去cur = head; while(cur){struct Node* copy = cur -> next;if(cur -> random == NULL){copy -> random = NULL;}else{copy -> random = cur -> random -> next;}cur = copy -> next;}

---

（2）第三步：復(fù)制結(jié)點(diǎn)解下來連接成一個新鏈表，恢復(fù)原鏈表鏈接關(guān)系

---

---

第三步代碼實(shí)現(xiàn) ： 如下（示例）：

 // 3.第三步：把拷貝結(jié)點(diǎn)解下來，鏈接成新的鏈表，同時恢復(fù)原鏈表cur = head;struct Node* copyhead = NULL ,*copytail =NULL;while(cur){struct Node* copy = cur -> next;struct Node* next = copy -> next;if(copytail == NULL){copytail = copyhead = copy;}else{copytail -> next = copy;copytail = copy;}//恢復(fù)原鏈表的犍cur -> next = next;cur = next ;}

---

3.整體源代碼

整體源代碼 ： 如下（示例）：

struct Node 
{int val;struct Node *next;struct Node *random;
};
struct Node* copyRandomList(struct Node* head) 
{//1.第一步：先把原來的拷貝一份struct Node* cur = head;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy -> next = cur -> next;cur -> next = copy;copy -> val = cur -> val;cur = copy -> next;}// 2.第二步：把random拷貝過去cur = head; while(cur){struct Node* copy = cur -> next;if(cur -> random == NULL){copy -> random = NULL;}else{copy -> random = cur -> random -> next;}cur = copy -> next;}// 3.第三步：把拷貝結(jié)點(diǎn)解下來，鏈接成新的鏈表，同時恢復(fù)原鏈表cur = head;struct Node* copyhead = NULL ,*copytail =NULL;while(cur){struct Node* copy = cur -> next;struct Node* next = copy -> next;if(copytail == NULL){copytail = copyhead = copy;}else{copytail -> next = copy;copytail = copy;}//恢復(fù)原鏈表的犍cur -> next = next;cur = next ;}return copyhead;
}

---

總結(jié)

以上就是今天要講的內(nèi)容，本文介紹了【Leedcode】數(shù)據(jù)結(jié)構(gòu)中鏈表必備的面試題（第五期）。
如果我的博客對你有所幫助記得三連支持一下，感謝大家的支持！