文章目錄
- 復制帶隨機指標的鏈表
- 題目
- 思想
- ==普通拷貝==
- ==順藤摸瓜==（這個是真的奇兵記，暗度陳倉的感覺）
- ==脫褲子還需提褲子人==（上面暗度陳倉，這個就是單刀直入）
- 代碼實作
- ==cur為NULL的時候就是停止copy的時候==
- ==有人說為什么不在上面malloc節點的時候就鏈，因為那時候小孩還沒出生你就讓你的還在上學嗎，沒錯為了卷你們，我準備偷偷生個小孩==
復制帶隨機指標的鏈表
天下傻逼獨一個就是我，我忘記了選c語言，用c++結果錯誤看一臉懵逼
題目
這題鏈表的復制難的地方就是隨機指標random 如何復制他的指向，很多人的確想到了malloc節點，我也想到了malloc一個一個的節點，但是基本所有人都卡死在這里了，就是我們如何鏈，在這里我們就會又遇到先天性大佬的天賦思維力的壓制，上一題是空間聯想的壓制，（來吧我小碼農就喜歡給先天以及后天的大佬錘煉）
思想
普通拷貝
實際上想到這樣也已經了不起了，有點磨具雛形了
順藤摸瓜（這個是真的奇兵記，暗度陳倉的感覺）
脫褲子還需提褲子人（上面暗度陳倉，這個就是單刀直入）
代碼實作
cur為NULL的時候就是停止copy的時候
struct Node* cur = head;
if(!cur)
return NULL;
while(cur)
{
//每次我們都要malloc一個copy節點
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
//開始給資料
copy->val = cur->val;
//開始插入
copy->next = cur->next;
cur->next = copy;
//開始cur移動
cur = copy->next;
}
有人說為什么不在上面malloc節點的時候就鏈，因為那時候小孩還沒出生你就讓你的還在上學嗎，沒錯為了卷你們，我準備偷偷生個小孩
//節點copy好后開始random相鏈
cur = head;
while(cur)
{
//重新把之前開辟的節點給copy維護
struct Node* copy = cur->next;
if(cur->random == NULL)
copy->random = NULL;
else
copy->random = cur->random->next;//上面的GIF的核心代碼
cur = copy->next;
}
然后拿下來一個個尾插，就是單刀直入你要還原原來的鏈表順序
//開始一個一個尾插起來
struct Node* copyHead = NULL;
struct Node* copyTail = NULL;
cur = head;
while(cur)
{
//重新把之前開辟的節點給copy維護
struct Node* copy = cur->next;
//這邊你需要一個next來還原原來鏈表順序，你不能用完人家對人家不負責任
struct Node* next = copy->next;
if(copyHead == NULL)
{
copyHead = copy;
copyTail = copy;
}
else
{
copyTail->next = copy;
copyTail = copy;
}
cur->next = next;//這一步看你對原來鏈表負不負責任
cur = next;
}
return copyHead;
struct Node* copyRandomList(struct Node* head) {
struct Node* cur = head;
if(!cur)
return NULL;
while(cur)
{
//每次我們都要malloc一個copy節點
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
//開始給資料
copy->val = cur->val;
//開始插入
copy->next = cur->next;
cur->next = copy;
//開始cur移動
cur = copy->next;
}
//節點copy好后開始random相鏈
cur = head;
while(cur)
{
//重新把之前開辟的節點給copy維護
struct Node* copy = cur->next;
if(cur->random == NULL)
copy->random = NULL;
else
copy->random = cur->random->next;//上面的GIF的核心代碼
cur = copy->next;
}
//開始一個一個尾插起來
struct Node* copyHead = NULL;
struct Node* copyTail = NULL;
cur = head;
while(cur)
{
//重新把之前開辟的節點給copy維護
struct Node* copy = cur->next;
//這邊你需要一個next來還原原來鏈表順序，你不能用完人家對人家不負責任
struct Node* next = copy->next;
if(copyHead == NULL)
{
copyHead = copy;
copyTail = copy;
}
else
{
copyTail->next = copy;
copyTail = copy;
}
cur->next = next;//這一步看你對原來鏈表負不負責任
cur = next;
}
return copyHead;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/340745.html
標籤：其他
上一篇：“解包”宏引數
下一篇：作業系統之行程執行緒篇