在这个问题中，我们给出了一个链表。我们的任务是创建一个程序来反转链表。

该程序将反转给定的链表并返回反转后的链表。

链表是一个包含项目的链接序列。每个链接包含到另一个链接的连接。

示例

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

输出

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

输出

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