138. 復(fù)制帶隨機(jī)指針的鏈表
給定一個鏈表，每個節(jié)點包含一個額外增加的隨機(jī)指針煤墙，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點沈撞。
要求返回這個鏈表的 深拷貝扣甲。
我們用一個由 n 個節(jié)點組成的鏈表來表示輸入/輸出中的鏈表担平。每個節(jié)點用一個 [val, random_index] 表示：
val：一個表示 Node.val 的整數(shù)却特。
random_index：隨機(jī)指針指向的節(jié)點索引（范圍從 0 到 n-1）救崔；如果不指向任何節(jié)點翘骂，則為 null 壁熄。
image.png
思路
本題難點是找到原始節(jié)點的random節(jié)點
1 第一遍遍歷，深拷貝每一個節(jié)點碳竟，使原始節(jié)點的next指向它的深拷貝節(jié)點草丧，深拷貝節(jié)點指向原始節(jié)點的原始next節(jié)點。這樣每個原始節(jié)點的next節(jié)點都是它的深拷貝節(jié)點
即n1->n1'->n2->n2'->null
2 第二遍遍歷莹桅，使深拷貝節(jié)點的random節(jié)點指向原始節(jié)點的random節(jié)點的next節(jié)點（也就是原始節(jié)點random的深拷貝節(jié)點）
3 斷開兩個鏈表
代碼
class Solution {
public Node copyRandomList(Node head) {
if (head == null){
return null;
}
//1 將所有節(jié)點昌执，深拷貝出一個節(jié)點，放在該節(jié)點后诈泼。注意這樣就可以通過p.next找到節(jié)點的深拷貝節(jié)點
Node p = head;
while (p != null){
Node cp = new Node(p.val);
cp.next = p.next;
p.next = cp;
p = p.next.next;
}
//2 給深拷貝節(jié)點的random復(fù)制
p = head;
while (p != null){
if(p.random != null) {
p.next.random = p.random.next;
}else {
p.next.random = null;
}
p = p.next.next;
}
//3 斷開兩個鏈表
p = head;
Node p2 = head.next;
Node newHead = p.next;
while (p2.next != null){
p.next = p2.next;
p = p.next;
p2.next = p.next;
p2 = p2.next;
}
p.next = null;
return newHead;
}
}
