題目描述（中等難度）
給一個鏈表挺份，返回復制后的鏈表褒翰。鏈表節(jié)點相對于普通的多了一個 random 指針，會隨機指向鏈表內的任意節(jié)點或者指向 null匀泊。
思路分析
這道題其實和 133 題 復制一個圖很類似优训，這里的話就是要解決的問題就是，當更新當前節(jié)點的 random 指針的時候各聘，如果 random 指向的是很后邊的節(jié)點揣非，但此時后邊的節(jié)點還沒有生成，那么我們該如何處理躲因。
和 133 題 一樣早敬，我們可以利用 HashMap 將節(jié)點提前生成并且保存起來，第二次遍歷到他的時候直接從 HashMap 里邊拿即可大脉。
這里的話就有兩種思路搞监，一種需要遍歷兩邊鏈表，一種只需要遍歷一遍镰矿。
2020.3.3 更新琐驴，leetcode 增加了樣例，之前沒有重復的數字所以
key存的val秤标，現在有了重復數字绝淡，將key修改為Node。此外Node的無參的構造函數也被去掉了抛杨，也需要修改够委。
解法一
首先利用 HashMap 來一個不用思考的代碼。
遍歷第一遍鏈表怖现，我們不考慮鏈表之間的相互關系，僅僅生成所有節(jié)點，然后把它存到 HashMap 中屈嗤，val 作為 key潘拨，Node 作為 value。
遍歷第二遍鏈表饶号，將之前生成的節(jié)點取出來铁追，更新它們的 next 和 random 指針。
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
HashMap<Node, Node> map = new HashMap<>();
Node h = head;
while (h != null) {
Node t = new Node(h.val);
map.put(h, t);
h = h.next;
}
h = head;
while (h != null) {
if (h.next != null) {
map.get(h).next = map.get(h.next);
}
if (h.random != null) {
map.get(h).random = map.get(h.random);
}
h = h.next;
}
return map.get(head);
}
解法二
解法一雖然簡單易懂茫船，但還是有可以優(yōu)化的地方的琅束。我們可以只遍歷一次鏈表。
核心思想就是延遲更新它的 next算谈。
1 -> 2 -> 3
用 cur 指向已經生成的節(jié)點的末尾
1 -> 2
^
c
然后將 3 構造完成
最后將 2 的 next 指向 3
1 -> 2 -> 3
^
c
期間已經生成的節(jié)點存到 HashMap 中涩禀，第二次遇到的時候直接從 HashMap 中拿
看下代碼理解一下含義吧
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
HashMap<Node, Node> map = new HashMap<>();
Node h = head;
Node cur = new Node(-1); //空結點，dummy 節(jié)點然眼，為了方便頭結點計算
while (h != null) {
//判斷當前節(jié)點是否已經產生過
if (!map.containsKey(h)) {
Node t = new Node(h.val);
map.put(h, t);
}
//得到當前節(jié)點去更新它的 random 指針
Node next = map.get(h);
if (h.random != null) {
//判斷當前節(jié)點是否已經產生過
if (!map.containsKey(h.random)) {
next.random = new Node(h.random.val);
map.put(h.random, next.random);
} else {
next.random = map.get(h.random);
}
}
//將當前生成的節(jié)點接到 cur 的后邊
cur.next = next;
cur = cur.next;
h = h.next;
}
return map.get(head);
}
解法三
上邊的兩種解法都用到了 HashMap 艾船，所以額外需要 O(n) 的空間復雜度。現在考慮不需要額外空間的方法高每。
主要參考了這里屿岂。主要解決的問題就是我們生成節(jié)點以后，當更新它的 random 的時候鲸匿，怎么找到之前生成的節(jié)點爷怀，前兩種解法用了 HashMap 全部存起來，這里的話可以利用原來的鏈表的指針域带欢。
主要需要三步运授。
- 生成所有的節(jié)點，并且分別插入到原有節(jié)點的后邊
- 更新插入節(jié)點的
random - 將新舊節(jié)點分離開來
一圖勝千言洪囤，大家看一下下邊的圖吧徒坡。
代碼對應如下。
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node l1 = head;
Node l2 = null;
//生成所有的節(jié)點瘤缩，并且分別插入到原有節(jié)點的后邊
while (l1 != null) {
l2 = new Node(l1.val);
l2.next = l1.next;
l1.next = l2;
l1 = l1.next.next;
}
//更新插入節(jié)點的 random
l1 = head;
while (l1 != null) {
if (l1.random != null) {
l1.next.random = l1.random.next;
}
l1 = l1.next.next;
}
l1 = head;
Node l2_head = l1.next;
//將新舊節(jié)點分離開來
while (l1 != null) {
l2 = l1.next;
l1.next = l2.next;
if (l2.next != null) {
l2.next = l2.next.next;
}
l1 = l1.next;
}
return l2_head;
}
解法四
不利用額外的空間復雜度還有一種思路喇完，參考 這里。
解法三利用原鏈表的 next 域把新生成的節(jié)點保存了起來剥啤。類似的锦溪，我們還可以利用原鏈表的 random 域把新生成的節(jié)點保存起來。
主要還是三個步驟府怯。
- 生成所有的節(jié)點刻诊，將它們保存到原鏈表的
random域，同時利用新生成的節(jié)點的next域保存原鏈表的random牺丙。 - 更新新生成節(jié)點的
random指針则涯。 - 恢復原鏈表的
random指針复局，同時更新新生成節(jié)點的next指針。
一圖勝千言粟判。
相應的代碼如下亿昏。
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node l1 = head;
Node l2 = null;
//生成所有的節(jié)點，講它們保存到原鏈表的 random 域档礁，
//同時利用新生成的節(jié)點的 next 域保存原鏈表的 random角钩。
while (l1 != null) {
l2 = new Node(l1.val);
l2.next = l1.random;
l1.random = l2;
l1 = l1.next;
}
l1 = head;
//更新新生成節(jié)點的 random 指針。
while (l1 != null) {
l2 = l1.random;
l2.random = l2.next != null ? l2.next.random : null;
l1 = l1.next;
}
l1 = head;
Node l2_head = l1.random;
//恢復原鏈表的 random 指針呻澜，同時更新新生成節(jié)點的 next 指針递礼。
while (l1 != null) {
l2 = l1.random;
l1.random = l2.next;
l2.next = l1.next != null ? l1.next.random : null;
l1 = l1.next;
}
return l2_head;
}
總
解法一、解法二是比較直接的想法羹幸，直接利用 HashMap 存儲之前的節(jié)點脊髓。解法三、解法四利用原有鏈表的指針睹欲，通過指來指去完成了賦值供炼。鏈表操作的核心思想就是，在改變某一個節(jié)點的指針域的時候窘疮，一定要把該節(jié)點的指針指向的節(jié)點用另一個指針保存起來袋哼，以免造成丟失。
更多詳細通俗題解詳見 leetcode.wang 闸衫。
