Créer une LinkedList inverse en C ++ à partir d’une LinkedList donnée

Je ne parviens pas à créer une liste chaînée dans l’ordre inverse à partir d’une liste chaînée donnée.

Je viens d’un milieu java et je viens de commencer à faire du C ++.

Pouvez-vous consulter mon code et voir ce qui ne va pas? Je suppose que je manipule simplement le pointeur et ne crée rien de nouveau.

//this is a method of linkedlist class, it creates a reverse linkedlist //and prints it void LinkedList::reversedLinkedList() { Node* revHead; //check if the regular list is empty if(head == NULL) return; //else start reversing Node* current = head; while(current != NULL) { //check if it's the first one being added if(revHead == NULL) revHead = current; else { //just insert at the beginning Node* tempHead = revHead; current->next = tempHead; revHead = current; } current = current->next; }//end while //now print it cout << "Reversed LinkedList: " << endl; Node* temp = revHead; while(temp != NULL) { cout <firstName << endl; cout <lastName << endl; cout <next; } }//end method

Plus facile: parcourez votre liste de liens, sauvegardez les nœuds précédent et suivant et laissez simplement le nœud actuel pointer sur le nœud précédent:

 void LinkedList::reversedLinkedList() { if(head == NULL) return; Node *prev = NULL, *current = NULL, *next = NULL; current = head; while(current != NULL){ next = current->next; current->next = prev; prev = current; current = next; } // now let the head point at the last node (prev) head = prev; }

 Node* revHead; // ... while(current != NULL) { //check if it's the first one being added if(revHead == NULL)

Vous revHead pas revHead mais vous l’utilisez. (J’espère qu’il est déjà clair pour vous que revHead est une variable locale utilisée pour stocker une adresse de mémoire et non quelque chose qui existe en dehors de la méthode / procédure)

La classe de stockage de revHead est automatique (c’est-à-dire dans le scope-body local). En C++ lorsque vous faites une telle déclaration, il n’est pas garanti que la valeur sera 0 .

(sauf si la classe de stockage est de type static ou si la variable est global elle est automatiquement initialisée à 0 si aucune autre valeur n’est fournie. Dans votre cas, la variable a une classe de stockage de type auto ce qui signifie qu’elle est définie localement dans une fonction, et lors de la déclaration d’une variable locale sans spécifier de valeur, la valeur est “garbage” (gardez à l’esprit qu’avec la prochaine norme C++0x Standard C++0x le mot clé auto a une nouvelle signification).

La valeur dans votre cas est garbage, ce qui fait échouer le if . Voir plus d’informations ici: Lien

Fait une

 Node* revHead = NULL;

Gardez à l’esprit que vous pourriez peut-être avoir des erreurs comme celle-ci dans une autre partie de votre code.

Une autre méthode consiste à parcourir la liste en premier et à stocker toutes les données dans une stack, puis à créer une nouvelle liste et à y insérer les données en partant du haut de la stack. La stack LIFO vous donnera les données dans l’ordre inverse. liste inversée.

Ceci est fait en utilisant seulement deux variables temporaires.

 Node* list::rev(Node *first) { Node *a = first, *b = first->next; while(a->next!=NULL) { b = a->next; a->next = a->next->next; b->next = first; first = b; } return first; }

En outre, vous pouvez le faire en utilisant la récursivité.

Je ne suis pas sûr, mais je pense que vous voulez une liste doublement chaînée où le noeud a un next et un précédent. Cela ne fonctionnera pas avec un pointeur externe sur la liste. Vous n’aurez pas l’adresse du noeud précédent.

Sinon, utilisez la méthode ci-dessus avec une stack, c’est une bonne suggestion.

 NODE * ReverseLinkedList(NODE * head){ if (head == NULL) return NULL; NODE * previous = NULL; while (head != NULL) { // Keep next node since we trash the next pointer. NODE *next = head->pNext; // Switch the next pointer to point backwards. head->pNext = previous; // Move both pointers forward. previous = head; head = next; } return previous; }

L’exemple ci-dessous utilise la récursivité pour inverser une liste de liens. J’ai demandé à ce Qs lors d’un entretien d’embauche. Cela a été testé et fonctionne. ListElem est le nœud.

 void LinkList::reverse() { if(pFirst == NULL) return; ListElem* current = pFirst; revCur(NULL, current, NULL); } void LinkList::revCur(ListElem *prev, ListElem* current, ListElem* next) { // ListElem *prev = NULL, *current = NULL, *next = NULL; if ( current != NULL ) { next = current->next; current->next = prev; prev = current; current = next; pFirst = prev; this->revCur(prev,current,next); } }

Ce qui précède est l’inverse de la liste de liens

 void LinkList::rev() { if(pFirst == NULL) return; ListElem *prev = NULL, *current = NULL, *next = NULL; current = pFirst; while(current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } // now let the head point at the last node (prev) pFirst = prev; }

  #include  /* this is a generic (structure agnostic) routine for reversing a singly linked list. 1st argument is the memory address the structure is located at, and 2nd argument is the memory address to this particular structure's NEXT member. */ void *rsll(void *struct_address, void *next_address /*(void **)*/) { uint32_t offset, holder; offset = next_address - struct_address; void **p = struct_address, *progress = NULL; while(p) { void *b; holder = (uint32_t)p; holder += offset; p = (void**)holder; //&(N->next) b = *p; //(N->next) *p = progress; //(N->next) holder = (uint32_t)p; holder -= offset; p = (void**)holder; //N progress = p; p = b; } return progress; } #include  int main() { struct list_t { int integer; struct list_t *next; }; struct list_t d = {40,NULL}, c = {30,&d}, b = {23,&c}, a = {10,&b}; struct list_t *list; list = &a; list = rsll(list,&(list->next)); while(list) { printf("%d\n",list->integer); list = list->next; } return 0; }