反向链接列表的C程序

在这个问题上，我们得到了一个链表。我们的任务是创建一个用于反向链接列表的程序。

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

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

示例

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

反向链接列表是通过反转列表的链接而创建以形成链接列表的链接列表。链表的头节点将是链表的最后一个节点，而最后一个将是头节点。

示例

由上述链表形成的反向链表-

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

为了反转给定的链表，我们将使用三个额外的指针。指针将在当前之前，之后。

我们将在开始时将上一个和后一个初始化为NULL，然后将当前初始化为链表的开头。

此后，我们将迭代直到达到初始值（非反向链表）的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("\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
Reverse Linked List : 85 10 65 32 9