Как скопировать связанный список в другой список?

Question

Я изучаю структуры данных и связанные списки, но я не понимаю, как сделать копию связанного списка. Может кто-нибудь объяснить это, возможно, используя псевдокод или код C?

Answer 1

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

1. Клон пустого списка - пустой список.
2. Клон спискас первым узлом x и оставшимися узлами xs является копией x, добавленной к клону xs.

Если вы кодируете связанный список в C ++, это может быть очень чисто:

struct Node {
    int value;
    Node* next;
};

Node* Clone(Node* list) {
    if (list == NULL) return NULL;

    Node* result = new Node;
    result->value = list->value;
    result->next = Clone(list->next);
    return result;
}

Answer 2

Вы понимаете, как добавить новый узел в существующий список? И понимаете ли вы, как пройти (т.е. перебрать) список? Копирование списка - это просто выполнение обеих этих операций одновременно (обход списка ListA; для каждого элемента скопируйте элемент и добавьте его как новый узел в ListB).