Leetcode 138. Copy List with Random Pointer

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.
問題:ランダムなポインタを持つチェーンテーブルを深くコピーします.
構想:最初は以前の深さコピー図のやり方に従って、深さ優先検索を利用してhashmapを結合したが、スタックオーバーフローのバグに遭遇した.なぜなら、このチェーンテーブルのランダムポインタは無限に循環する可能性があるからだ.例えば、AはランダムにBを指し、BはランダムにAを指す.次はバグのあるコードです.
public RandomListNode copyRandomList(RandomListNode head) {

    Map map = new HashMap<>();

    return copyHelper(head, map);
}

private RandomListNode copyHelper(RandomListNode node, Map 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;
}

バグが何であるかを意識した後,randomによるデッドサイクルを回避する方法を考え,実際にはノードごとに最大1つのrandomポインタしかないことを考え,randomを検索タスクに追加する必要はない.チェーンテーブルを巡回し、マッピング関係を確立してから、クローンノードを一度巡回して接続できます.
public RandomListNode copyRandomList(RandomListNode head) { if (head == null) { return null; }

    HashMap map = new HashMap<>();
    RandomListNode dummy = head;
    while (dummy != null) {
        RandomListNode copy = new RandomListNode(dummy.label);
        map.put(dummy, copy);
        dummy = dummy.next;
    }

    Queue 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);
}