138. Copy List with Random Pointer
Дан связный список длиной 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# решение
сопоставлено/оригинал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++ решение
auto-draft, проверить перед отправкой#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 решение
сопоставлено/оригинал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 решение
сопоставлено/оригинал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 решение
сопоставлено/оригинал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 nodeGo решение
сопоставлено/оригинал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)
}Algorithm
1️⃣
Инициализация и начало обхода:
Начните обход графа со стартового узла (head). Создайте словарь visited_dictionary для отслеживания посещенных и клонированных узлов.
2️⃣
Проверка и клонирование узлов:
Для каждого текущего узла (current_node) проверьте, есть ли уже клонированная копия в visited_dictionary.
Если клонированная копия существует, используйте ссылку на этот клонированный узел.
Если клонированной копии нет, создайте новый узел (cloned_node_for_current_node), инициализируйте его и добавьте в visited_dictionary, где ключом будет current_node, а значением — созданный клон.
3️⃣
Рекурсивные вызовы для обработки связей:
Сделайте два рекурсивных вызова для каждого узла: один используя указатель random, другой — указатель next.
Эти вызовы отражают обработку "детей" текущего узла в терминах графа, где детьми являются узлы, на которые указывают указатели random и next.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.