<劍指offer>翻版題 leetcode138. 複制帶随機指針的連結清單

題目

給你一個長度為 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 作為傳入參數。

代碼

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	 struct Node*cur=head;
     //1.連結拷貝節點
     while(cur!=NULL)
     {
         struct Node*next=cur->next;
         struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
         copy->next=NULL;
         copy->random=NULL;
         copy->val=cur->val;
         cur->next=copy;
         copy->next=next;
         cur=next;
     }
     // 2.找到copy->random節點位置
     cur=head;
     while(cur!=NULL)
     {
         struct Node*copy=cur->next;
         if(cur->random==NULL)
         {
             copy->random=NULL;
         }
         else
         {
             copy->random=cur->random->next;
         }
         cur=cur->next->next;
     }
     //3.拆分拷貝連結清單
     cur=head;
     struct Node*copyhead=NULL;
     struct Node*copytail=NULL;
     while(cur!=NULL)
     {
         struct Node*copy=cur->next;
         struct Node*next=copy->next;
         cur->next=next;
         //尾插
         if(copytail==NULL)
         {
              copyhead=copytail=copy;
         }
         else
         {
             copytail->next=copy;
             copytail=copy;
         }
         cur=next;
     }
     return copyhead;
}

           

過程分析

1. 連結拷貝節點

2.尋找拷貝節點的random

1.cur->random為空時

copy->random也應指向NULL的後面，即copy->random==NULL

2.cur->random不為空

3.拆分拷貝連結清單