題目描述：
給定一個鏈表，每個節(jié)點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。
要求返回這個鏈表的 深拷貝。
我們用一個由 n 個節(jié)點組成的鏈表來表示輸入/輸出中的鏈表。每個節(jié)點用一個 [val, random_index] 表示：
val：一個表示 Node.val 的整數(shù)。
random_index：隨機指針指向的節(jié)點索引（范圍從 0 到 n-1）；如果不指向任何節(jié)點，則為 null 。
思路一：Hash
使用hash表這種數(shù)據(jù)結(jié)構(gòu)。hash-key存儲原鏈表的節(jié)點，hash-value則對應(yīng)存儲復(fù)制的節(jié)點。通過key-value的對應(yīng)關(guān)系，可以推斷:
node'.next = map.get(node.next);
且有:
node'.rand = map.get(node.rand);
代碼如下：
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
HashMap<Node,Node> map = new HashMap<>();
Node cur = head;
while(cur != null){
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur = head;
while(cur != null){
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
時間復(fù)雜度：O(N)
額外空間復(fù)雜度：O(N)
代碼執(zhí)行結(jié)果：
思路二：指針思路，不使用額外的數(shù)據(jù)空間
現(xiàn)有帶有rand指針的鏈表如下,橙色為rand,藍色為next：
先不考慮rand指針，我們將鏈表復(fù)制成如下結(jié)構(gòu),紅色node為復(fù)制的部分：
當形成這種結(jié)構(gòu)的鏈表時，其實也就等同于hash表了。不難看出,復(fù)制的節(jié)點的next指針與rand指針應(yīng)該如何指向，代碼如下：
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
Node cur = head;
Node next = null;
while(cur != null){
next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
cur = head;
while(cur != null){
cur.next.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;
}
cur = head;
Node res = head.next;
Node curCopy = null;
while(cur != null){
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = curCopy.next == null ? null : curCopy.next.next;
cur = next;
}
return res;
}
}
時間復(fù)雜度：O(N)
額外空間復(fù)雜度：O(1)
代碼執(zhí)行結(jié)果：
