Как добавить связанный список к себе?

Question

Учитывая, что это моя функция:

void addtoSameList(const List &another){
   for (Node *temp = new Node(*head); temp != nullptr; temp = temp -> next){
      Node *ptr = other.head;
      Node *temp2 = new Node;
      temp2->value = temp->value;
      while (ptr -> next != nullptr) {
         ptr = ptr -> next;
      }
      ptr->next = temp2;
      temp2->next = nullptr;
   }
   return;
}

, где моя цель - добавить связанный список к себе, я не знаю точно, что идет не так. Если, например, у меня есть связанный список с именем n в основной функции, где я затем объявляю:

n.addtoSameList(n);

, означая, что & other будет указывать на тот же узел, что и n, я подумал, чтосоздайте новый узел и глубоко скопируйте содержимое n.

Тем не менее, два моих вывода: либо я попал в бесконечный цикл, либо какой-то узел пропускается.

Какисправить эту проблему?

Answer 1

Этот код имеет множество проблем. Во-первых, интерфейс не предполагает, что единственное использование - добавить связанный список к себе. Он также не предполагает, что глубокая копия необходима в любом другом случае.

Итак, давайте скорректируем требования ...

Требуется функция-член, которая добавит копию связанного спискак существующему. Тогда случай самозаполнения естественным образом выпадает из описания проблемы.

Подход здесь будет заключаться в том, чтобы проходить через связанный список, тщательно копируя каждый узел, затем повторно настраивая указатели наосновной связанный список, указывающий на ваш новый узел, и указатель в новом узле, который должен быть установлен в конец списка. Это сохраняет инвариант списка по мере прохождения списка.

Здесь есть подводный камень. Если вы добавляете себя, вы рискуете создать бесконечный цикл. Таким образом, вы должны найти конечный узел переданного списка, прежде чем начинать этот процесс, и последовательно использовать его, чтобы выяснить, добрались ли вы до конца списка. Если вы поддерживаете указатель на хвост, это тривиально. Если вы этого не сделаете, это означает обход списка.

Другим способом было бы просто создать сначала копию, тщательно поддерживая указатель на первый узел копии. Затем просто настройте следующий указатель хвостового узла так, чтобы он указывал на новый список, а затем настройте хвостовой узел (если этот указатель поддерживается в структуре данных LinkedList) так, чтобы он указывал на хвостовой узел копии. И это, вероятно, путь, которым вы должны идти. Это чище и эффективнее. Основным недостатком является очистка при обработке исключений. Но на вашем уровне вы не должны беспокоиться об этом прямо сейчас.

Answer 2

Вот альтернативный подход. Создайте три указателя: ptrBegin, ptrEnd и ptrNew. ptrBegin указывает на начало связанного списка и пересекает связанный список, так что ptrEnd и ptrNew указывают на последний элемент связанного списка. Затем увеличивайте ptrBegin до ptrBegin != ptrEnd, одновременно копируя данные в ptrBegin в новый узел в ptrNew->next и увеличивая ptrNew.