C-Programm zum Umkehren der verknüpften Liste

In dieser Frage erhalten wir eine verknüpfte Liste. Unsere Aufgabe besteht darin, ein Programm zum Umkehren einer verknüpften Liste zu erstellen.

Dieses Programm kehrt die angegebene verknüpfte Liste um und gibt die umgekehrte verknüpfte Liste zurück.

Eine verknüpfte Liste ist eine verknüpfte Sequenz mit Elementen. Jeder Link enthält eine Verbindung zu einem anderen Link.

Beispiel

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

Umgekehrte verknüpfte Liste besteht darin, eine verknüpfte Liste zu erstellen, indem die Verknüpfungen der verknüpften Liste umgekehrt werden. Der Hauptknoten der verknüpften Liste wird zum letzten Knoten der verknüpften Liste und der letzte Knoten wird zum Hauptknoten.

Beispiel

Invertierte verknüpfte Liste, die aus der oben verknüpften Liste gebildet wurde −

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

Um die angegebene verknüpfte Liste umzukehren, verwenden wir drei zusätzliche Zeiger zur Verarbeitung. Diese Zeiger sind „Vorherig“, „Nachher“ und „Aktuell“.

Wir werden zunächst sowohl previous als auch after auf NULL setzen und current auf den Kopf der verknüpften Liste setzen.

Danach iterieren wir, bis wir NULL der ursprünglich verknüpften Liste erreichen. Dann machen Sie Folgendes:

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

Jetzt erstellen wir ein Programm zum Umkehren der verknüpften Liste. Es gibt zwei Möglichkeiten, dieses Programm zu erstellen: eine iterative und eine rekursive.

Programm zum Umkehren einer verknüpften Liste (tail-rekursive Methode)

Beispiel

Demonstration

#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;
}

Ausgabe

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

Programm zum Umkehren einer verknüpften Liste (iterative Methode)

Beispiel

Re Allzeitdemonstration

#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;
}

Ausgabe

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

Das obige ist der detaillierte Inhalt vonC-Programm zum Umkehren der verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!