Copy List with Random Pointer

Средняя№138старый узел → новый

Дан связный список: у каждого узла кроме next есть ссылка random на любой узел этого же списка или на none. Нужно сделать полную копию: новые узлы с теми же значениями, и все ссылки копии ведут на новые узлы, а не на старые. Наш пример: 3 → 8 → 5 → 1, random 3 → 5, 8 → 3, 5 → none, 1 → 1 (на себя).

138 Copy List with Random PointerРазбор · 1×

Пример: список 3 → 8 → 5 → 1; дуги — ссылки random. Копия нарисована снизу, её узлы помечены ′.

listcopynone3851
исходный списокnode и его копиякопия, ещё без ссылоккопия со ссылками

Пустой словарь: для каждого старого узла он будет хранить его копию

01/34
сначала · назад · пуск · шаг
Скорость
1function copyRandomList(head):
2 copy = empty map // copy[none] = none
3 node = head
4 while node is not none:
5 copy[node] = new node(node.val)
6 node = node.next
7 node = head
8 while node is not none:
9 copy[node].next = copy[node.next]
10 copy[node].random = copy[node.random]
11 node = node.next
12 return copy[head]
состояние
node
–
copy
{}
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. random может смотреть вперёд, на узел, у которого копии ещё нет. Поэтому первый проход только делает копии, а второй связывает их, когда все копии уже есть.
  2. Словарь «старый узел → его копия» превращает каждую ссылку в один поиск: копия node.random — это copy[node.random], искать по списку не нужно.
  3. Каждая ссылка копии берётся из словаря, а в словаре только новые узлы, поэтому из копии нельзя попасть в старый список.

Сложность

Время O(n): два прохода по списку, каждый поиск в словаре — O(1). Память O(n): в словаре по записи на узел, не считая самой копии.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.