問題描述：
輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針random指向一個(gè)隨機(jī)節(jié)點(diǎn)），請(qǐng)對(duì)此鏈表進(jìn)行深拷貝，并返回拷貝后的頭結(jié)點(diǎn)。
示例：
輸入：{1,2,3,4,5,3,5,#,2,#}
輸出：{1,2,3,4,5,3,5,#,2,#}
解析:我們將鏈表分為兩段，前半部分{1,2,3,4,5}為
ListNode，后半部分{3,5,#,2,#}是隨機(jī)指針域表示。以上示例前半部分可以表示鏈表為的
ListNode：1->2->3->4->5后半部分3，5，#，2，#分別表示為：1的位置指向3，2的位置指向5，3的位置指向
null，4的位置指向2，5的位置指向null解法：
hash表輔助存儲(chǔ)法思路：遍歷原鏈表，在遍歷的過(guò)程中判斷原鏈表的當(dāng)前節(jié)點(diǎn)是否存在復(fù)制節(jié)點(diǎn)，存在將復(fù)制鏈表的前序節(jié)點(diǎn)
next指針指向該復(fù)制的節(jié)點(diǎn)（從hash表取出），不存在則以當(dāng)前節(jié)點(diǎn)的內(nèi)容創(chuàng)建新的復(fù)制節(jié)點(diǎn)，復(fù)制鏈表的前序節(jié)點(diǎn)的next指針指向它，并將節(jié)點(diǎn)地址映射關(guān)系存儲(chǔ)進(jìn)hash表。其次判斷原鏈表的當(dāng)前節(jié)點(diǎn)的random指針指向的節(jié)點(diǎn)是否存在復(fù)制節(jié)點(diǎn)，存在將復(fù)制鏈表的前序節(jié)點(diǎn)的next節(jié)點(diǎn)的random指針指向該復(fù)制的節(jié)點(diǎn)（從hash表取出），不存在則以當(dāng)前節(jié)點(diǎn)的random節(jié)點(diǎn)內(nèi)容創(chuàng)建新的復(fù)制節(jié)點(diǎn)，復(fù)制鏈表的前序節(jié)點(diǎn)的next節(jié)點(diǎn)的random指針指向它，并將節(jié)點(diǎn)地址映射關(guān)系存儲(chǔ)進(jìn)hash表。原鏈表的當(dāng)前節(jié)點(diǎn)curr和復(fù)制鏈表的前序節(jié)點(diǎn)prev步進(jìn)，循環(huán)以上的操作直到curr為null時(shí)間復(fù)雜度：O(n), 遍歷一次原鏈表的時(shí)間
空間復(fù)雜度：O(n), 哈希表使用的空間注意事項(xiàng)：
- 題意為深拷貝，所以復(fù)制鏈表的節(jié)點(diǎn)不能有指向原鏈表同位置節(jié)點(diǎn)的指針
- 特例情況的處理，這里要為復(fù)制鏈表創(chuàng)建虛擬頭結(jié)點(diǎn)好為前序節(jié)點(diǎn)
prev初始賦值鏈表拼接、拆分
思路：這種方法需要遍歷三次鏈表。定義一個(gè)游標(biāo)指針
curr，指向原鏈表的頭結(jié)點(diǎn)，第一次遍歷原鏈表，遍歷的過(guò)程中將經(jīng)過(guò)的節(jié)點(diǎn)復(fù)制并鏈接到被復(fù)制節(jié)點(diǎn)的后面：原節(jié)點(diǎn)->復(fù)制節(jié)點(diǎn)->原節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)，curr指針步進(jìn)，待遍歷完整個(gè)鏈表，此時(shí)鏈表的節(jié)點(diǎn)數(shù)翻倍，一前一后包含原節(jié)點(diǎn)和復(fù)制出的新節(jié)點(diǎn)。將curr指針復(fù)位到頭結(jié)點(diǎn)，第二次遍歷更新過(guò)后的鏈表，這次是將復(fù)制節(jié)點(diǎn)的random指針賦值，判斷當(dāng)前節(jié)點(diǎn)的random節(jié)點(diǎn)是否為空，如果不為空則將當(dāng)前節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)的random指針指向?yàn)楫?dāng)前節(jié)點(diǎn)的random節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)。來(lái)到第三次遍歷，此時(shí)跟第二次遍歷一樣，定義三個(gè)指針p1、p2和復(fù)制出的鏈表的頭結(jié)點(diǎn)指針newHead，p1指向當(dāng)前鏈表的頭節(jié)點(diǎn)，p2和newHead指向頭結(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)，p1、p2的后續(xù)節(jié)點(diǎn)指向?yàn)樗鼈兒罄m(xù)節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)，完后分別步進(jìn)到新的后續(xù)節(jié)點(diǎn)，當(dāng)p2的后續(xù)節(jié)點(diǎn)不為空的時(shí)候如此往復(fù)。待遍歷完后將p1的后續(xù)節(jié)點(diǎn)指向空（null）完成拆分，返回復(fù)制鏈表的頭結(jié)點(diǎn)newHead時(shí)間復(fù)雜度：O(n), 遍歷了三次鏈表
空間復(fù)雜度：O(1), 使用了常數(shù)個(gè)鏈表指針變量注意事項(xiàng)：
- 第三次遍歷完后注意將鏈接原鏈表的游標(biāo)指針指向
null
解法一
圖示：
代碼
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
// 原鏈表的當(dāng)前節(jié)點(diǎn)初始賦值
RandomListNode curr = pHead;
// 偽造一個(gè)頭節(jié)點(diǎn)，避免處理特例情況
RandomListNode dummyHead = new RandomListNode(Integer.MIN_VALUE);
// 前序節(jié)點(diǎn)初始賦值
RandomListNode prev = dummyHead;
// 創(chuàng)建一個(gè)hash表，用于存儲(chǔ)原節(jié)點(diǎn)和復(fù)制節(jié)點(diǎn)的映射關(guān)系，例如A->A'
Map<RandomListNode, RandomListNode> map = new HashMap<>();
// 遍歷原鏈表
while (curr != null) {
// 如果hash表中不存在原鏈表當(dāng)前節(jié)點(diǎn)的復(fù)制節(jié)點(diǎn)則以當(dāng)前節(jié)點(diǎn)的內(nèi)容創(chuàng)建新的復(fù)制節(jié)點(diǎn)，復(fù)制鏈表的前序節(jié)點(diǎn)的next指針指向它，并將節(jié)點(diǎn)地址映射關(guān)系存儲(chǔ)進(jìn)hash表
if (!map.containsKey(curr)) {
prev.next = new RandomListNode(curr.val);
map.put(curr, prev.next);
} else {// 如果hash表中存在原鏈表當(dāng)前節(jié)點(diǎn)的復(fù)制節(jié)點(diǎn)，則復(fù)制鏈表的前序節(jié)點(diǎn)的next指針指向該復(fù)制節(jié)點(diǎn)
prev.next = map.get(curr);
}
// 如果hash表中不存在原鏈表當(dāng)前節(jié)點(diǎn)的random指針指向節(jié)點(diǎn)的復(fù)制節(jié)點(diǎn)則以當(dāng)前節(jié)點(diǎn)的random節(jié)點(diǎn)內(nèi)容創(chuàng)建新的復(fù)制節(jié)點(diǎn)，復(fù)制鏈表的前序節(jié)點(diǎn)的next節(jié)點(diǎn)的random指針指向它，并將節(jié)點(diǎn)地址映射關(guān)系存儲(chǔ)進(jìn)hash表
if (!map.containsKey(curr.random) && curr.random != null) {
prev.next.random = new RandomListNode(curr.random.val);
map.put(curr.random, prev.next.random);
} else {// 如果hash表中存在原鏈表當(dāng)前節(jié)點(diǎn)的random節(jié)點(diǎn)的復(fù)制節(jié)點(diǎn)，則復(fù)制鏈表的前序節(jié)點(diǎn)的next節(jié)點(diǎn)的random指針指向該復(fù)制節(jié)點(diǎn)
prev.next.random = map.get(curr.random);
}
// 步進(jìn)原鏈表的當(dāng)前節(jié)點(diǎn)
curr = curr.next;
// 步進(jìn)復(fù)制鏈表的前序節(jié)點(diǎn)
prev = prev.next;
}
// 返回復(fù)制鏈表的真實(shí)頭結(jié)點(diǎn)
return dummyHead.next;
}
}
解法二
圖示
代碼
/*
class RandomListNode {
RandomListNode(int val) {
this.val = val;
}
int val;
RandomListNode next;
RandomListNode random;
}
*/
public class Solution {
public RandomListNode copyRandomList(RandomListNode pHead) {
if (pHead == null) {
return null;
}
RandomListNode curr = pHead;
while (curr != null) {
RandomListNode newNode = new RandomListNode(curr.val);
newNode.next = curr.next;
curr.next = newNode;
curr = newNode.next;
}
curr = pHead;
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}
RandomListNode newHead = pHead.next;
RandomListNode p1 = pHead;
RandomListNode p2 = p1.next;
while (p2.next != null) {
p1.next = p1.next.next;
p2.next = p2.next.next;
p1 = p1.next;
p2 = p2.next;
}
// 注意斷開原鏈表最末節(jié)點(diǎn)和新鏈表最末節(jié)點(diǎn)的連接
p1.next = null;
return newHead;
}
}
