目錄
- 前言
- 一、復雜帶隨機指標鏈表題鏈接
- 題目描述
- 題目思路
- 總結
前言
😂這方法太棒了！
一、復雜帶隨機指標鏈表題鏈接
題目描述
給你一個長度為 n 的鏈表，每個節點包含一個額外增加的隨機指標 random ，該指標可以指向鏈表中的任何節點或空節點，
構造這個鏈表的 深拷貝，
深拷貝應該正好由 n 個 全新 節點組成，其中每個新節點的值都設為其對應的原節點的值，新節點的 next 指標和 random 指標也都應指向復制鏈表中的新節點，并使原鏈表和復制鏈表中的這些指標能夠表示相同的鏈表狀態，復制鏈表中的指標都不應指向原鏈表中的節點 ，
測驗樣例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：val全相同
| 輸入：head = [[3,null],[3,0],[3,null]] |
|---|
| 輸出：[[3,null],[3,0],[3,null]] |
測驗樣例4：為空
| 輸入：head = [] |
|---|
| 輸出：NULL |
題目思路
- 對于鏈表，最好的方法就是開辟空間
- 除了空，其他節點都另外開辟一個空間，來重新連接這個鏈表
- 然后通過原鏈表節點的random的指向來連接新開辟中random的關系
4.最后來連接 開辟的新節點，重新連接老鏈表
注意：頭節點為空的時候
代碼如下：
struct Node* copyRandomList(struct Node* head)
{
if(head==NULL)
return NULL;
//開辟空間
struct Node*copy=NULL;
struct Node*cur=head;
while(cur)
{
struct Node*next=cur->next;
copy=(struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
copy->next=next;
cur->next=copy;
cur=next;
}
cur=head;
copy=cur->next;
while(cur)
{
copy=cur->next;
if(cur->random!=NULL)
{
copy->random=cur->random->next;
}
else
{
copy->random=cur->random;
}
cur=copy->next;
}
//鏈接random
struct Node*guardHead=NULL;
struct Node*guardTail=NULL;
struct Node*liberate=NULL;
guardTail=guardHead=liberate=(struct Node*)malloc(sizeof(struct Node));
cur=head;
while(cur)
{
copy=cur->next;
cur->next=copy->next;
guardTail->next=copy;
guardTail=copy;
cur=copy->next;
}
guardHead=guardHead->next;
free(liberate);
return guardHead;
}
總結
🤣就是玩！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/276314.html
標籤：其他