Comment copier une liste liée dans une autre liste?

Question

J'étudie des structures de données et des listes liées, mais je ne comprends pas comment faire une copie d'une liste chaînée. Quelqu'un peut-il expliquer cela, éventuellement en utilisant un pseudocode ou un code C?

Answer 1

La logique de la duplication d'une liste chaînée est récursive et sur la base des observations suivantes:

1. Le clone de la liste vide est la liste vide.
2. Le clonage d'une liste avec le premier nœud x et les nœuds restants xs est une copie de x ajoutée à un clone de xs.

Si vous encodez la liste chaînée en C++, cela peut être très propre:

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

Savez-vous comment ajouter un nouveau nœud à une liste existante? Et comprenez-vous comment parcourir (c'est-à-dire parcourir) une liste? La copie d'une liste consiste simplement à effectuer ces deux opérations simultanément (traverse ListA, pour chaque élément, copie l'élément et l'ajoute en tant que nouveau nœud à ListB).