題目內容：

138. 隨機鏈表的復制 - 力扣（LeetCode）

分析：?

這道題目，第一眼感覺非常亂，這是正常的，但是我們經過仔細分析示例明白后，其實也并不是那么難。現在讓我們一起來分析分析吧！

1.題目要求的是鏈表的復制，那么我們得想我們該怎么做，才能很好地進行下去呢？

2.是直接把原鏈表一個一個地移動過來？這思路果斷不對，它還要保持原來的鏈表不被復制啊.

3.經過觀察，我們發現13的random指向7。各種穿插的，所以我們采用

?

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

復制部分：

先在每個數復制下來，分別放在它的原數字的下一個。即下圖：

4.接著你看它原鏈表的那些數字。7的random指向NULL，13的random指向7.（其他的省略說）。7的next指向13。看到這種規律，我們試想是不是可以把復制的也弄成這樣子，就形成了一個獨立的復制鏈表了，對吧？?

連線部分：

?

 //連接線cur=head;while(cur){struct Node* copy=cur->next;// struct Node* Next=cur->next->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=cur->next->next;}

如下圖：

你看復制完了之后，是不是可以直接它復制那部分挪下來，它也是不會破壞原鏈表的，這是不是就符合題目要求了對吧？

5.完成了這步了之后，到了我們一個一個挪的那部分了。

如下圖：

?

解釋上圖：

 //復制的挪下來，恢復原鏈表struct Node* copyhead=NULL,*copytail=NULL;cur=head; while(cur){struct Node* copy=cur->next;struct Node* Next=copy->next; //尾插if(copyhead==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}

挪動部分：

當我們復制完了之后，開始挪新的復制鏈表：

1.首先定義一個cur指針指向head頭。再定義一個next指針指向cur的下一個（方便它隨時都能返回找到copy的位置）。

2.定義兩個指針分別為copyhead和copytail指針，放在新的鏈表那里當作移動工具和最后返回工具

2.接著，相當于進行尾插，當?第一次時，copyhead和copytail都為空時，就把copy值直接放到這個指針

3.不為空時，就把copy值放到copytail的下一位。

恢復部分：

最后，恢復原來的鏈表，即去掉它copy的那些數：

1.因為我們上面都沒有動過cur的位置，所以這里就直接使用cur這個指針就行了。

2.把cur的下一個給Next即：? 把cur的下一個next給給cur的next的next（即cur的下下個）。

  //恢復鏈表cur->next=Next;cur=Next; 

總代碼：?

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {//復制struct Node* cur=head;while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;struct Node*Next=cur->next;cur->next=copy;copy->next=Next;cur=Next;}//連接線cur=head;while(cur){struct Node* copy=cur->next;// struct Node* Next=cur->next->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=cur->next->next;}//復制的挪下來，恢復原鏈表struct Node* copyhead=NULL,*copytail=NULL;cur=head; while(cur){struct Node* copy=cur->next;struct Node* Next=copy->next; //尾插if(copyhead==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}//恢復鏈表cur->next=Next;cur=Next; }return copyhead;
}

最后，特別要注意的是：cur的位置要每到一部分都要及時更新變成head。（因為它每一部分都在改變），不然就會像我一開始那樣，發現怎么都不正確哇哇哇哇。

每次雞湯：

好啦，到了我們的每次雞湯部分：

雖然我每次邁出的那一步都很小，但是終究會有那么一天會到達終點的。加油吧，青年。