Алгоритмы Java: Копирование списка со случайным указателем. Решаем задачи с LeetCode на Java.

*“LeetCode” – это на самом деле жаргональное выражение, дословно «элитный код». l33t speak – это явление вроде нашего «албанского» у них.

Описание задачи:

Дан связный список длины n. Каждый узел содержит дополнительный случайный указатель который может указывать на любой узел списка или на Null.

@javatg – разбор задач с собеседований на Java

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

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

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

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

  • – val: целое число, представляющее Node.val
  • – random_index: индекс узла (диапазон от 0 до n-1), на который указывает random или null, если он не указывает ни на один узел.

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

Пример 1:

Алгоритмы Java: Копирование списка со случайным указателем. Решаем задачи с LeetCode на Java.
Ввод: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Вывод: [[7,null],[13,0],[11,4],[10,2],[1,0]] 

Пример 2:

Алгоритмы Java: Копирование списка со случайным указателем. Решаем задачи с LeetCode на Java.
Ввод: head = [[1,1],[2,1]]
Вывод: [[1,1],[2,1]]

Пример 3:

Алгоритмы Java: Копирование списка со случайным указателем. Решаем задачи с LeetCode на Java.
Ввод: head = [[3,null],[3,0],[3,null]]
Вывод: [[3,null],[3,0],[3,null]]

Ограничения:

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • Node.random являеться или Null или указывает на какой-то из узлов в связанном списке. 

Рассуждение:

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

  1. Нужно создать копию каждого узла с тем же значением, что и у исходного узла.
  2. Нужно установить указатели на следующий узел таким же образом, как и в исходном узле.
  3. Нужно установить указатели на случайный узел таким же образом, как и на исходный узел.

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

Предпосылка:

Если вы хотите отлаживать свой код – что я лично вам рекомендую – вы должны ввести данный класс

Алгоритмы Java: Копирование списка со случайным указателем. Решаем задачи с LeetCode на Java.

класс узла

Решение:

Начнём с решения первой подзадачи. Давайте сделаем простую вещь – выполним итерацию по связанному списку и создадим копию для каждого узла в нём. Я выбрал HashMap для сохранения пар типа старый узел –> новый узел. Пока мы выполняем итерацию от заголовка листа к окончанию, давайте введём temp и назначим её заголовком листа.

Алгоритмы Java: Копирование списка со случайным указателем. Решаем задачи с LeetCode на Java.

Мы решили первую подзадачу. Вас удивит, насколько легко мы решим две следующие. У нас уже есть связи между старыми узлами и новыми. Нам нужно только заполнить указатели на следующий узел и случайный указатель. Наша карта уже хранит всю необходимую информацию. Давайте снова назначим temp заголовком листа. Давайте также создадим фиктивный узел который будет хранить ссылку на нашу свежескопированный заголовок. Последнее, что нам нужно, это указатель prev, который поможет нам установить связь узел -> следующий узел.

Наши решения должны выглядеть следующим образом:

Алгоритмы Java: Копирование списка со случайным указателем. Решаем задачи с LeetCode на Java.

Приведенный выше код дает нам линейную временную и пространственную сложность.

+1
0
+1
0
+1
0
+1
0
+1
0

Ответить

Ваш адрес email не будет опубликован. Обязательные поля помечены *