??前段時間在做一個項目薄扁，所以沒有時間做面試題听怕，最近才將那個科創(chuàng)項目做的差不多了，于是開始做面試題了扁誓。
題意：
給出一個鏈表防泵，每個節(jié)點包含一個額外增加的隨機指針可以指向鏈表中的任何節(jié)點或空的節(jié)點。
返回一個深拷貝的鏈表蝗敢。
挑戰(zhàn)：
可否使用O(1)的空間
??可能是好久沒有做面試題了捷泞，所以手有點生疏了，這么簡單的一道題寿谴，做起來都有一點費勁锁右。
1.常規(guī)解法(哈希表)
(1).概述
??這個題用哈希表解決是非常簡單的，理解起來也非常的簡單的讶泰。
??哈希表解法的思路：
??第一步咏瑟，將原鏈表從頭遍歷，然后將每個節(jié)點深拷貝一份(這里的深拷貝意思：創(chuàng)建一個新的節(jié)點痪署，里面的值用原節(jié)點的值一樣)码泞，然后將這個新的節(jié)點放入哈希表中，其中key為原節(jié)點狼犯，value為新的節(jié)點余寥；
??第二步，從頭再遍歷原鏈表悯森，每次遍歷從哈希表中取以當(dāng)前節(jié)點為key的新節(jié)點宋舷，獲得新的節(jié)點之后，新的節(jié)點的next為當(dāng)前節(jié)點的next為key的新節(jié)點呐馆，新的節(jié)點的random也是如此肥缔×ぃ可能這里看起來有點費勁汹来，不要緊，待會參考代碼就會明白了改艇。
(2).代碼
public RandomListNode copyRandomList(RandomListNode head) {
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode p = head;
while (p != null) {
RandomListNode newListNode = new RandomListNode(p.label);
//以當(dāng)前的原節(jié)點為key收班，新節(jié)點為value
map.put(p, newListNode);
p = p.next;
}
p = head;
while (p != null) {
//獲取以當(dāng)前的原節(jié)點為key的新節(jié)點
RandomListNode q = map.get(p);
//新節(jié)點的next
q.next = map.get(p.next);
//新節(jié)點的random
q.random = map.get(p.random);
p = p.next;
}
return map.remove(head);
}
2.非常規(guī)解法
(1).概述
??這種解法主要是為了完成該題的挑戰(zhàn)項。
??這種解法理解起來相對來說有點難度谒兄，其實就是代碼的可讀性不是很容易摔桦，如果理解了方法的思想，代碼理解起來就非常的容易。
??這里的解釋邻耕，我用幾張圖片先來展示一下鸥咖，其實就是參考了這位大佬的博客：地址
??第一步，將每個原節(jié)點的next指向?qū)?yīng)的節(jié)點兄世，這個相對應(yīng)的節(jié)點的next指向原節(jié)點的原next啼辣。
原來的鏈表
??經(jīng)過第一步的變換之后
變換之后
??第二步,給新節(jié)點的random賦值
變換之后
??第三步,恢復(fù)兩個鏈表的next
恢復(fù)之后
(2).代碼
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
RandomListNode p = head;
//第一步，將原節(jié)點的next指向?qū)?yīng)的新節(jié)點
//新節(jié)點的next指向原節(jié)點的原next
while (p != null) {
RandomListNode newP = new RandomListNode(head.label);
newP.next = p.next;
p.next = newP;
p = newP.next;
}
//第二步御滩，參照原節(jié)點的random指向鸥拧，改變新節(jié)點的random指向
p = head;
while (p != null) {
//p.next 就是當(dāng)前節(jié)點對應(yīng)的新節(jié)點
p.next.random = p.random == null ? null : p.random.next;
p = p.next.next;
}
//第三步，恢復(fù)
RandomListNode newHead = head.next;
p = head;
RandomListNode q = newHead;
while (p != null) {
p.next = q.next;
if (q.next != null) {
q.next = q.next.next;
}
p = p.next;
q = q.next;
}
return newHead;
}
