Скопировать список с ссылкой на случайный элемент

Задача.

Дан связный список, в котором каждый элемент списка имеет ссылку на следующий элемент списка и ссылку на случайный элемент из этого же списка. Нужно сделать deep copy этого списка. Копия должна содержать в точности n полностью новых элементов списка, где n это размер исходного списка. Каждый новый элемент должен содержать соответствующее значение из элемента старого списка, а также иметь ссылки на следующий и случайный элемент в новом списке. Элементы нового списка не должны содержать ссылки на элементы из старого списка.

Решение.

Класс элемента списка:

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

Пример такого списка:

Если бы не было этого усложнения со ссылкой на случайный элемент списка, то можно было бы просто пройтись циклом по списку, на каждом шаге делать копию элемента, а также хранить предыдущий скопированный элемент, чтобы выставить ему ссылку на следующий новый элемент.

Но т.к. даже самый первый элемент может иметь ссылку на элемент из середины или конца списка, а у нас еще нет ее копии, то такой алгоритм не подойдет.

Поэтому мы может разбить алгоритм на два этапа. Вначале, пройдем циклом по списку, для каждого элемента будем делать копию, но не будем высталять ссылки на следующий и случайный элемент. Но при этом сохраним маппинг старого элемента на новый.
На втором этапе снова пройдем по старому списку и уже имея все копии и маппинг выставим ссылки на следующий и случайный элемент списка.

После первого цикла:

После второго выставим ссылки:

public Node copyRandomList(Node head) {
    //Маппинг старых элементов списка на новые (копии)
    Map<Node, Node> oldToNew = new HashMap<>();
    //Проходим циклом по списку и создаем копии,
    //но без ссылок на следующий и случайный элементы списка
    //Также сохраняем маппинг старых вершин на новые
    Node current = head;
    while (current != null) {
        Node copy = new Node(current.val);
        oldToNew.put(current, copy);
        current = current.next;
    }
    //Во втором цикле проставляем ссылки на следующий и случайный 
    //элемент списка
    current = head;
    while (current != null) {
        Node copy = oldToNew.get(current);
        copy.next = oldToNew.get(current.next);
        copy.random = oldToNew.get(current.random);
        current = current.next;
    }
    return oldToNew.get(head);
}

Time Complexity O(n), Space Complexity O(n).