Programme C pour inverser la liste chaînée

Dans cette question, on nous donne une liste chaînée. Notre tâche est de créer un programme pour inverser une liste chaînée.

Ce programme inversera la liste chaînée donnée et renverra la liste chaînée inversée.

Une liste chaînée est une séquence liée contenant des éléments. Chaque lien contient une connexion vers un autre lien.

Exemple

9 -> 32 -> 65 -> 10 -> 85 -> NULL

Liste chaînée inversée consiste à créer une liste chaînée en inversant les liens de la liste chaînée. Le nœud principal de la liste chaînée deviendra le dernier nœud de la liste chaînée, et le dernier nœud deviendra le nœud principal.

Exemple

Liste chaînée inversée formée à partir de la liste chaînée ci-dessus −

85 -> 10 -> 65 -> 32 -> 9 -> NULL

Pour inverser la liste chaînée donnée, nous utiliserons trois pointeurs supplémentaires à traiter. Ces pointeurs sont précédents, après et actuels.

Nous définirons initialement previous et after sur NULL, et définirons current en tête de la liste chaînée.

Après cela, nous itérons jusqu'à atteindre NULL de la liste chaînée initiale. Ensuite, procédez comme suit :

after = current ->
next current ->
next = previous
previous = current
current = after

Créons maintenant un programme pour inverser la liste chaînée. Il existe deux manières de créer ce programme, l’une itérative et l’autre récursive.

Programme pour inverser une liste chaînée (méthode récursive de queue)

Exemple

Démonstration

#include <stdio.h>
struct Node {
   int data;
   struct Node* next;
};
Node* insertNode(int key) {
   Node* temp = new Node;
   temp->data = key;
   temp->next = NULL;
   return temp;
}
void tailRecRevese(Node* current, Node* previous, Node** head){
   if (!current->next) {
      *head = current;
      current->next = previous;
      return;
   }
   Node* next = current->next;
   current->next = previous;
   tailRecRevese(next, current, head);
}
void tailRecReveseLL(Node** head){
   if (!head)
      return;
   tailRecRevese(*head, NULL, head);
}
void printLinkedList(Node* head){
   while (head != NULL) {
      printf("%d ", head->data);
      head = head->next;
   }
   printf("</p><p>");
}
int main(){
   Node* head1 = insertNode(9);
   head1->next = insertNode(32);
   head1->next->next = insertNode(65);
   head1->next->next->next = insertNode(10);
   head1->next->next->next->next = insertNode(85);
   printf("Linked list : \t");
   printLinkedList(head1);
   tailRecReveseLL(&head1);
   printf("Reversed linked list : \t");
   printLinkedList(head1);
   return 0;
}

Sortie

Linked list : 9 32 65 10 85
Reversed linked list : 85 10 65 32 9

Programme pour inverser une liste chaînée (méthode itérative)

Exemple

Réel- démonstration du temps

#include <stdio.h>
struct Node {
   int data;
   struct Node* next;
   Node(int data){
      this->data = data;
      next = NULL;
   }
};
struct LinkedList {
   Node* head;
   LinkedList(){
      head = NULL;
   }
   void interReverseLL(){
      Node* current = head;
      Node *prev = NULL, *after = NULL;
      while (current != NULL) {
         after = current->next;
         current->next = prev;
         prev = current;
         current = after;
      }
      head = prev;
   }
   void print() {
      struct Node* temp = head;
      while (temp != NULL) {
         printf("%d ", temp-> data);
         temp = temp->next;
      }
      printf("</p><p>");
   }
   void push(int data){
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList linkedlist;
   linkedlist.push(85);
   linkedlist.push(10);
   linkedlist.push(65);
   linkedlist.push(32);
   linkedlist.push(9);
   printf("Linked List : \t");
   linkedlist.print();
   linkedlist.interReverseLL();
   printf("Reverse Linked List : \t");
   linkedlist.print();
   return 0;
}

Sortie

Linked List : 9 32 65 10 85
Reverse Linked List : 85 10 65 32 9

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!