Рубрики

Клонировать связанный список со следующим и случайным указателем | Комплект 1

Вам предоставляется двойной список ссылок с одним указателем каждого узла, указывающим на следующий узел, как в одном списке ссылок. Однако второй указатель МОЖЕТ указывать на любой узел в списке, а не только на предыдущий узел. Теперь напишите программу за O (n) раз, чтобы продублировать этот список. То есть напишите программу, которая создаст копию этого списка.

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

фигура 1

Произвольные указатели показаны красным, а следующие указатели — черным

Метод 1 (использует O (n) дополнительное пространство)
Этот метод сначала сохраняет в массиве следующее и произвольное сопоставления (из исходного списка), затем изменяет исходный связанный список (для создания копии), создает копию. И наконец восстанавливает первоначальный список.

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

фигура 2

4) Измените указатель арбитра всех узлов в связанном списке копирования, чтобы он указывал на соответствующий узел в исходном связанном списке.
5) Теперь создайте указатель арбитра в списке связанных копий, как показано ниже, и восстановите следующий указатель узлов в исходном связанном списке.

       copy_list_node->arbit =
                      copy_list_node->arbit->arbit->next;
       copy_list_node = copy_list_node->next; 

6) Восстановите следующие указатели в исходном связанном списке из сохраненных сопоставлений (на шаге 2).

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Метод 2 (использует постоянное дополнительное пространство)
Спасибо Сараванан Мани за предоставление этого решения. Это решение работает с использованием постоянного пространства.
1) Создайте копию узла 1 и вставьте ее между узлом 1 и узлом 2 в исходный связанный список, создайте копию 2 и вставьте ее между 2 и 3. Продолжайте таким же образом, добавьте копию N после N-го узла
2) Теперь скопируйте произвольную ссылку таким способом

     original->next->arbitrary = original->arbitrary->next;  /*TRAVERSE 
TWO NODES*/

Это работает, потому что original-> next — это не что иное, как копия оригинала, а Original-> произвольный-> следующий — не что иное, как копия произвольного.
3) Теперь восстановите исходные и скопируйте связанные списки таким образом в одном цикле.

     original->next = original->next->next;
     copy->next = copy->next->next;

4) Убедитесь, что последний элемент original-> next равен NULL.

Обратитесь к сообщению ниже для реализации этого метода.
Клонировать связанный список со следующим и случайным указателем в пространстве O (1)

Сложность времени: O (n)
Вспомогательное пространство: O (1)

См. Следующий пост для реализации на основе хеширования.
Клонировать связанный список со следующим и случайным указателем | Набор 2

На вопрос Варуна Бхатии. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Клонировать связанный список со следующим и случайным указателем | Комплект 1

0.00 (0%) 0 votes