A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
題意：深度復制一個帶隨機指針的鏈表份企。
思路：
開始是按照之前深度復制圖的做法茵休，利用深度優(yōu)先搜索結合hashmap，但是遇到了棧溢出的bug榕莺，原因是這個鏈表的隨機指針有可能會無限循環(huán)，比如A隨機指向B钉鸯，B隨機指向A。下面是有bug的代碼：
public RandomListNode copyRandomList(RandomListNode head) {
Map<RandomListNode, RandomListNode> map = new HashMap<>();
return copyHelper(head, map);
}
private RandomListNode copyHelper(RandomListNode node, Map<RandomListNode, RandomListNode> map) {
if (node == null) {
return null;
}
if (map.containsKey(node)) {
return map.get(node);
}
RandomListNode copyNode = new RandomListNode(node.label);
copyNode.next = copyHelper(node.next, map);
copyNode.random = copyHelper(node.random, map);
map.put(node, copyNode);
return copyNode;
}
意識到bug是什么以后贸营，就考慮如何避免random導致的死循環(huán)岩睁，想到了其實每個節(jié)點最多只有一個random指針，沒必要把random加到搜索任務中捕儒。可以先遍歷鏈表阎毅，建立映射關系，然后再遍歷一次扇调，把克隆節(jié)點連接起來抢肛。
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode dummy = head;
while (dummy != null) {
RandomListNode copy = new RandomListNode(dummy.label);
map.put(dummy, copy);
dummy = dummy.next;
}
Queue<RandomListNode> q = new LinkedList<>();
q.offer(head);
while (!q.isEmpty()) {
RandomListNode cur = q.poll();
RandomListNode copy = map.get(cur);
if (cur.next != null) {
copy.next = map.get(cur.next);
q.offer(cur.next);
}
if (cur.random != null) {
copy.random = map.get(cur.random);
}
}
return map.get(head);
}