C program to reverse linked list

In this problem, we are given a linked list. Our task is to create a program to reverse a linked list.

This program will reverse the given linked list and return the reversed linked list.

Linked list is a linked sequence containing items. Each link contains a connection to another link.

Example

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

Reverse linked list is a linked list that is created by reversing the links of the linked list. The head node of the linked list will become the last node of the linked list, and the last node will become the head node.

Example

Inverted linked list formed from the above linked list −

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

In order to reverse the given linked list, we will use three additional pointers to process. These pointers are previous, after and current.

We will initially set both previous and after to NULL, and set current to the head of the linked list.

After this, we iterate until we reach NULL of the initial linked list. Then do the following:

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

Now let us create a program for reversing the linked list. There are two ways to create this program, one is iterative and the other is recursive.

Program to reverse linked list (tail recursive method)

Example

Demonstration

#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;
}

Output

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

Program to reverse linked list (iterative method)

Example

Real-time demonstration

#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;
}

Output

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

The above is the detailed content of C program to reverse linked list. For more information, please follow other related articles on the PHP Chinese website!