DEV Community

faangmaster
faangmaster

Posted on

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

Задача.

Дан связный список, в котором каждый элемент списка имеет ссылку на следующий элемент списка и ссылку на случайный элемент из этого же списка. Нужно сделать 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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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

Image description

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

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

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

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

Image description

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

Image description

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

Enter fullscreen mode Exit fullscreen mode

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

Image of Datadog

The Future of AI, LLMs, and Observability on Google Cloud

Datadog sat down with Google’s Director of AI to discuss the current and future states of AI, ML, and LLMs on Google Cloud. Discover 7 key insights for technical leaders, covering everything from upskilling teams to observability best practices

Learn More

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up