138. Copy List with Random Pointer

leetcode medium

#csharp#graph#hash-table#leetcode#linked-list#medium#recursion

Task

Дан связный список длиной n, в котором каждый узел содержит дополнительный случайный указатель (random pointer), который может указывать на любой узел в списке или быть равным null.

Создайте глубокую копию списка. Глубокая копия должна состоять из ровно n совершенно новых узлов, где каждый новый узел имеет значение, равное значению соответствующего оригинального узла. Указатели next и random новых узлов должны указывать на новые узлы в скопированном списке таким образом, чтобы указатели в оригинальном и скопированном списке представляли одно и то же состояние списка. Ни один из указателей в новом списке не должен указывать на узлы в оригинальном списке.

Например, если в оригинальном списке есть два узла X и Y, где X.random --> Y, то для соответствующих узлов x и y в скопированном списке, x.random должен указывать на y.

Верните голову скопированного связного списка.

Связный список представлен во входных/выходных данных как список из n узлов. Каждый узел представлен парой [val, random_index], где:

val: целое число, представляющее Node.val

random_index: индекс узла (в диапазоне от 0 до n-1), на который указывает случайный указатель, или null, если он не указывает ни на какой узел.

Вашему коду будет дана только голова оригинального связного списка.

Пример:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

C# solution

matched/original

public class Node {
    public int val;
    public Node next;
    public Node random;
    public Node(int _val, Node _next, Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
}
public class Solution {
    private Dictionary<Node, Node> visitedHash = new Dictionary<Node, Node>();
    public Node CopyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (this.visitedHash.ContainsKey(head)) {
            return this.visitedHash[head];
        }
        Node node = new Node(head.val, null, null);
        this.visitedHash[head] = node;
        node.next = this.CopyRandomList(head.next);
        node.random = this.CopyRandomList(head.random);
        return node;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class Node {
    public int val;
    public Node next;
    public Node random;
    public Node(int _val, Node _next, Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
}
class Solution {
public:
    private unordered_map<Node, Node> visitedHash = new unordered_map<Node, Node>();
    public Node CopyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (this.visitedHash.count(head)) {
            return this.visitedHash[head];
        }
        Node node = new Node(head.val, null, null);
        this.visitedHash[head] = node;
        node.next = this.CopyRandomList(head.next);
        node.random = this.CopyRandomList(head.random);
        return node;
    }
}

Java solution

matched/original

public class Solution {
    HashMap<Node, Node> visitedHash = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        if (this.visitedHash.containsKey(head)) {
            return this.visitedHash.get(head);
        }

        Node node = new Node(head.val, null, null);
        this.visitedHash.put(head, node);

        node.next = this.copyRandomList(head.next);
        node.random = this.copyRandomList(head.random);

        return node;
    }
}

JavaScript solution

matched/original

function Node(val, next, random) {
    this.val = val;
    this.next = next;
    this.random = random;
}

var copyRandomList = function (head) {
    let visitedHash = new Map();
    let cloneNode = function (node) {
        if (node === null) {
            return null;
        }
        if (visitedHash.has(node)) {
            return visitedHash.get(node);
        }
        let newNode = new Node(node.val, null, null);
        visitedHash.set(node, newNode);
        newNode.next = cloneNode(node.next);
        newNode.random = cloneNode(node.random);
        return newNode;
    };
    return cloneNode(head);
};

Python solution

matched/original

class Solution:
    def __init__(self):
        self.visitedHash = {}

    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        if head == None:
            return None

        if head in self.visitedHash:
            return self.visitedHash[head]

        node = Node(head.val, None, None)
        self.visitedHash[head] = node
        node.next = self.copyRandomList(head.next)
        node.random = self.copyRandomList(head.random)

        return node

Go solution

matched/original

type Node struct {
    Val int
    Next *Node
    Random *Node
}

func copyRandomList(head *Node) *Node {
    visitedHash := map[*Node]*Node{}
    var cloneNode func(node *Node) *Node
    cloneNode = func(node *Node) *Node {
        if node == nil {
            return nil
        }
        if _, ok := visitedHash[node]; ok {
            return visitedHash[node]
        }
        newNode := &Node{Val: node.Val}
        visitedHash[node] = newNode
        newNode.Next = cloneNode(node.Next)
        newNode.Random = cloneNode(node.Random)
        return newNode
    }
    return cloneNode(head)
}

Explanation

Algorithm

1️⃣

Инициализация и начало обхода:

Начните обход графа со стартового узла (head). Создайте словарь visited_dictionary для отслеживания посещенных и клонированных узлов.

2️⃣

Проверка и клонирование узлов:

Для каждого текущего узла (current_node) проверьте, есть ли уже клонированная копия в visited_dictionary.

Если клонированная копия существует, используйте ссылку на этот клонированный узел.

Если клонированной копии нет, создайте новый узел (cloned_node_for_current_node), инициализируйте его и добавьте в visited_dictionary, где ключом будет current_node, а значением — созданный клон.

3️⃣

Рекурсивные вызовы для обработки связей:

Сделайте два рекурсивных вызова для каждого узла: один используя указатель random, другой — указатель next.

Эти вызовы отражают обработку "детей" текущего узла в терминах графа, где детьми являются узлы, на которые указывают указатели random и next.

😎