題目描述
138.復制帶隨機指標的鏈表
給你一個長度為 n 的鏈表，每個節點包含一個額外增加的隨機指標 random ，該指標可以指向鏈表中的任何節點或空節點，
構造這個鏈表的 深拷貝， 深拷貝應該正好由 n 個 全新 節點組成，其中每個新節點的值都設為其對應的原節點的值，新節點的 next 指標和 random 指標也都應指向復制鏈表中的新節點，并使原鏈表和復制鏈表中的這些指標能夠表示相同的鏈表狀態，復制鏈表中的指標都不應指向原鏈表中的節點 ，
例如，如果原鏈表中有 X 和 Y 兩個節點，其中 X.random -> Y ，那么在復制鏈表中對應的兩個節點 x 和 y ，同樣有 x.random -> y ，
回傳復制鏈表的頭節點，
用一個由 n 個節點組成的鏈表來表示輸入/輸出中的鏈表，每個節點用一個 [val, random_index] 表示：
val：一個表示 Node.val 的整數，
random_index：隨機指標指向的節點索引（范圍從 0 到 n-1）；如果不指向任何節點，則為 null ，
你的代碼 只 接受原鏈表的頭節點 head 作為傳入引數，
示例1：
輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例2：
輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]
題解
解決本題需要三步，
- 先將這個鏈表拷貝一層
- 再將拷貝出來的鏈表中的random進行連接
- 再將拷貝出來的鏈表與原鏈表進行斷開
初始情況：
①先將鏈表拷貝一層，讓頭指標cur的next指向一個新創建的拷貝結點，并將拷貝結點的next指向cur沒發生變化之前的next，即在每個結點的后邊再插入一個與他相同的結點，
cur一直向后走，一直重復①步驟即可得到拷貝結點（圖中米黃色線條）
②再將拷貝鏈表的random進行連接，由于原鏈表中每個結點的next都是拷貝鏈表中的結點，因此再將原鏈表中結點的random給拷貝鏈表的程序中，只需給random的next即可，（圖中紫色線條）
③將拷貝出來的鏈表與原鏈表進行斷開，即將拷貝結點的next指向原結點的next->next->next，即可完成斷開，回傳拷貝結點的頭即可(圖中橙色線條)
題解代碼
struct Node* copyRandomList(struct Node* head) {
struct Node* cur = head;
//先將這個鏈表拷貝一層
while(cur)
{
struct Node* tail = cur->next;
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->val = cur->val;
cur->next = newNode;
newNode->next = tail;
cur = tail;
}
cur = head;
//再將拷貝出來的鏈表中的random進行連接
while(cur)
{
struct Node* newHead = cur->next;
struct Node* tail = newHead->next;
if(cur->random == NULL)
{
newHead->random = NULL;
}
else{
newHead->random = cur->random->next;
}
cur = tail;
}
//將拷貝出的鏈表與原鏈表斷開鏈接
struct Node* newhead = NULL, *newTail = NULL;
cur = head;
while(cur)
{
struct Node* copy = cur->next;
struct Node* tail = copy->next;
cur->next = tail;
if(newhead == NULL)
{
newhead = newTail = copy;
}
else{
newTail->next = copy;
newTail = copy;
}
cur = tail;
}
return newhead;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260710.html
標籤：其他
上一篇：執行緒池學習Note
下一篇：HTTP和HTTPS