Reverse the Singly Linked List in C

Reverse the Singly Linked List in C

This article has given a singly linked list and will reverse the linked list by changing the links between nodes.

Example:

                        Input:  2 -> 4 -> 6 -> 8

                        Output: 8-> 6 -> 4 -> 2

Method 1: (Iterative Method)

• This method will initialize the three-pointer variable, e.g., curr as head of the linked list, next and pre as NULL.
• Then, we will traverse the linked list in a loop and do the following steps:
  • Before changing next of current,
  • store next node
  • next = curr->next
  • Now change next of current
  • This is where actual reversing happens
  • curr->next = pre
  • Move prev and curr one step forward
  • pre = curr
  • curr = next

Source code to implement the method 1 in C language:

 #include<stdio.h>
 #include<stdlib.h>
 struct node
 {
 int info;
 struct node *next;
 };
 struct node *start = NULL;
 // For inserting the elements in the linked list
 void add(int item)
 {
 struct node *t, *p;
 t = (struct node *)malloc( sizeof( struct node ));
 if(start == NULL)
 {
 start = t;
 start -> info = item;
 start -> next = NULL;
 return;
 }
 else
 {
 struct node *p = start;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 // For reversing the nodes of the linked list
 void reverse (struct node * t)
 {
     struct node *curr=t;
     struct node *next=NULL;
     struct node *pre=NULL;
     while(curr != NULL)
     {
         next=curr -> next;
         curr -> next = pre;
         pre = curr;
         curr = next;
    }
    start = pre;
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next != NULL)
                                     {
                         printf("%d -> ",t -> info);
                         t = t -> next;
                         }
                         printf("%d\n",t -> info);
 }
 // Driver Function
 int main()
 {
     int i;
     for (i = 2; i<12; i+=2)
     {
         add(i);
     }
     reverse(start);
     traverse(start);
     return 0;
 } 

Output: -

Time Complexity: O(n)

Space Complexity: O(1)

Method 2: (Recursive Method)

• Divide the list into two parts: The first parts store the first node, and the second part store the rest of the linked list.
• Call reverse function for the rest of the linked list.
• Link rest to first.
• Fix head pointer

Source Code to implement the method 2 in C language:

 #include<stdio.h>
 #include<stdlib.h>
 struct node
 {
 int info;
 struct node *next;
 };
 struct node *start = NULL;
 // For inserting the elements in the linked list
 void add(int item)
 {
 struct node *t, *p;
 t = (struct node *)malloc( sizeof( struct node ));
 if(start == NULL)
 {
 start = t;
 start -> info = item;
 start -> next = NULL;
 return;
 }
 else
 {
 struct node *p = start;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 // For reversing the nodes of the linked list
 struct node * reverse (struct node * t)
 {
     if( t == NULL || t -> next == NULL)
         return t;
      struct node * rest = reverse(t -> next);
      t -> next -> next = t;
      t -> next = NULL;
      return rest;
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next != NULL)
                                     {
                         printf("%d -> ",t -> info);
                         t = t -> next;
                         }
                         printf("%d\n",t -> info);
 }
 // Driver Function
 int main()
 {
     int i;
    for (i=1; i<6; i++)
     {
         add(i);
     }
     start = reverse(start);
     traverse(start);
     return 0;
 } 

Output: -

Time Complexity: O(n) 

Space Complexity: O(1)