反轉鍊錶的C程序

在這個問題中，我們給了一個鍊錶。我們的任務是建立一個程式來反轉鍊錶。

該程式將反轉給定的鍊錶並傳回反轉後的鍊錶。

鍊錶是一個包含項目的連結序列。每個連結包含到另一個連結的連接。

範例

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

反轉鍊錶是透過反轉鍊錶的連結來建立鍊錶的鍊錶。鍊錶的頭節點將成為鍊錶的最後一個節點，而最後一個節點將成為頭節點。

範例

從上述鍊錶中形成的反轉鍊錶 −

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

為了反轉給定的鍊錶，我們將使用三個額外的指標來處理。這些指針分別是previous、after和current。

我們將初始時將previous和after都設為NULL，將current設定為鍊錶的頭部。

在此之後，我們將迭代直到達到初始鍊錶的NULL。然後執行以下操作：

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

現在讓我們為反轉鍊錶建立一個程式。有兩種方法可以創建該程序，一種是迭代方法，另一種是遞歸方法。

反轉鍊錶的程式（尾遞歸方法）

範例

 示範

#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中文網其他相關文章！