複制帶隨機指針的鏈錶＜難度系數＞

題述：給你一個長度為 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 = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]

示例3：

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

示例4：
輸入：head = [ ]
輸出：[ ]

🧷 平臺：Visual studio 2017 && windows

核心思想：
思路一 (不實現)：1，先複制原鏈錶的每個節點，再把新節點鏈接起來 (拷貝節點與原節點沒有建立關系)；2，計算原鏈錶中的每個節點cur的random跟cur的相對距離；3，再去複制新鏈錶中找到當前節點相對距離的節點，賦值給random；找1個節點的random的時間複雜度是O(N)，找所有節點的random的時間複雜度是O(N^2)

思路二 (優化思路一)：1，在原鏈錶的每個節點的後面，鏈接插入一個拷貝節點 (建立相對關系，找random)；2，置random；3，把拷貝節點解下來，鏈接到一起，同時恢複原鏈錶；時間複雜度是O(N)

leetcode原題

#include<stdio.h>#include<stdlib.h>struct Node{	int val;	struct Node* next;	struct Node* random;};struct Node* copyRandomList(struct Node* head){	if(head == NULL)        return NULL;	//1.拷貝節點至每個原節點的後面    struct Node* cur = head;    while(cur)    {        //先保存下一個節點的地址        struct Node* next = cur->next;        //開避拷貝節點的空間        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));        //要保證val是相同的        copy->val = cur->val;        //修改原鏈錶的鏈接關系        cur->next = copy;        copy->next = next;        //迭代        cur = next;    }       //2.置random    cur = head;    while(cur)    {        //找拷貝節點        struct Node* copy = cur->next;        //鏈接random，當cur的random為空時，需要特殊處理        if(cur->random)            copy->random = cur->random->next;        else            copy->random = NULL;        //迭代        cur = copy->next;    }    //3.把拷貝節點解下來，尾插至新鏈錶(使用帶哨兵比特的頭節點)。順手複原原鏈錶，雖然題意並沒有要求    struct Node *copyhead, *copytail;    copyhead = copytail = (struct Node*)malloc(sizeof(struct Node));    cur = head;    while(cur)    {        //找拷貝節點        struct Node* copy = cur->next;         //保存原鏈錶的下一個節點的地址        struct Node* next = copy->next;        //尾插        copytail->next = copy;        copytail = copy;        //恢複原鏈錶        cur->next = next;        //迭代        cur = next;    }    //4.釋放空間    struct Node* temp = copyhead;    copyhead = copyhead->next;    free(temp);    return copyhead;}int main(){	struct Node* n1 = (struct Node*)malloc(sizeof(struct Node));	n1->val = 3;	struct Node* n2 = (struct Node*)malloc(sizeof(struct Node));	n2->val = 3;		struct Node* n3 = (struct Node*)malloc(sizeof(struct Node));	n3->val = 3;	n1->next = n2;	n2->next = n3;	n3->next = NULL;		n1->random = n3;	n2->random = n1;	n3->random = NULL;		copyRandomList(n1);	return 0;}