[leetcode] 138.復制帶隨機指標的鏈表（C語言）-有解無憂

題目描述：

給定一個鏈表，每個節點包含一個額外增加的隨機指標，該指標可以指向鏈表中的任何節點或空節點，

要求回傳這個鏈表的深拷貝，

我們用一個由 n 個節點組成的鏈表來表示輸入/輸出中的鏈表，每個節點用一個 [val, random_index] 表示：

val：一個表示 Node.val 的整數，
random_index：隨機指標指向的節點索引（范圍從 0 到 n-1）；如果不指向任何節點，則為 null ，

示例 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：
在這里插入圖片描述

輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]

示例 4：

輸入：head = []
輸出：[]
解釋：給定的鏈表為空（空指標），因此回傳 null，

方法：

第一步：
拷貝出新節點，鏈接到原節點的后面，拷貝節點的random先不處理，

在這里插入圖片描述
此部分代碼如下：

struct Node* cur=head;
    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        struct Node* next=cur->next;
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }

第二步：
處理拷貝節點的random，每個拷貝節點的random都為原節點的next節點

在這里插入圖片描述
此部分代碼如下：

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;
    }

第三步：
將拷貝節點鏈接在一起，恢復原鏈表
在這里插入圖片描述
此部分代碼如下：

cur=head;
    struct Node* newhead=NULL,* newtail=NULL;
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;
        cur->next=copy->next;
       if(newtail==NULL){
           newhead=newtail=copy;
       }
       else{
           newtail->next=copy;
           newtail=copy;
       }
       cur=next;
    }

下面給出完整代碼：

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur=head;
    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        struct Node* next=cur->next;
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }
    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;
    }
    cur=head;
    struct Node* newhead=NULL,* newtail=NULL;
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;
        cur->next=copy->next;
       if(newtail==NULL){
           newhead=newtail=copy;
       }
       else{
           newtail->next=copy;
           newtail=copy;
       }
       cur=next;
    }
    return newhead;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257758.html

標籤：其他

上一篇：【數學建模】2021美賽B題解題思路(森林大火及無人機布局)【含Matlab原始碼 247期】

下一篇：“離開公司，你什么都不是！” 對程式員來說平臺真的比技識訓重要嗎？