リンクリストを逆にするためのCプログラム

この問題では、リンクリストが提供されます。私たちの仕事は、リンクリストを逆にするためのプログラムを作成することです。

プログラムは、指定されたリンクリストを反転し、反転したリンクリストを返します。

リンクリスト アイテムを含むリンクのシーケンスです。各リンクには、別のリンクへの接続が含まれています。

例

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

逆リンク listは、リストのリンクを逆にすることによってリンクリストを形成するために作成されたリンクリストです。リンクリストのヘッドノードがリンクリストの最後のノードになり、最後のノードがヘッドノードになります。

例

上記のリンクリストから形成された逆リンクリスト-

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

指定されたリンクリストを逆にするために、処理中の3つの追加のポインターを使用します。ポインタは前、後、現在になります。

前と後を最初はNULLに初期化し、現在はリンクリストの先頭に初期化します。

この後、最初の（逆にされていないリンクリスト）のNULLに達するまで繰り返します。そして、次のことを行います-

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

次に、リンクリストを元に戻すためのプログラムを作成しましょう。プログラムを作成するには、2つの方法があります。1つは反復的で、もう1つは再帰的です。

リンクリストを逆にするためのプログラム（末尾再帰アプローチ）

例

#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("\n");
}
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;
}

出力

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

リンクリストを逆にするためのプログラム（反復アプローチ）

例

#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("\n");
   }
   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;
}

出力

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