逆リンクリストを作成する C プログラム

この問題では、リンクされたリストが与えられます。私たちのタスクは、リンクされたリストを逆にするプログラムを作成することです。

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

リンク リストは、項目を含むリンクされたシーケンスです。各リンクには、別のリンクへの接続が含まれています。

例

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

逆リンク リストは、リンク リストのリンクを逆にして作成されるリンク リストです。リンク リストの先頭ノードがリンク リストの最後のノードになり、最後のノードが先頭ノードになります。

例

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

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

指定されたリンク リストを逆にするために、3 つの追加ポインターを使用して処理します。これらのポインタは、前、後、および現在のものです。

最初に、previous と after の両方を NULL に設定し、current をリンクされたリストの先頭に設定します。

この後、最初のリンク リストの 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("</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;
}

出力

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("</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;
}

出力

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

以上が逆リンクリストを作成する C プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。