Program to Reverse a Linked List using Loop and Recursion

  • Write a C program to reverse a linked list using loop and recursion.

Given a singly linked list having N nodes, we have to reverse the sequence of nodes of given linked list. Here we will a linked list using both iterative and recursive approach. 

Input Linked List
1 -- > 3 --> 9 --> 12 --> 5 --> NULL
Reversed Linked List
5 --> 12 --> 9 --> 3 --> 1 --> NULL

Reverse a Linked List using Iteration

Algorithm to reverse a linked list using iteration
We will use three node pointer "previous", "current" and "next" to keep track of previous, current and next node during linked list reversal.
  • Initialize current pointer to head and previous pointer to NULL.
  • Traverse linked list from head till current->next != NULL.
  • In every iteration, set current->next = previous; and move all three pointers to next node.
  • Return previous pointer. This is the new head pointer of reversed linked list.
#include <stdio.h>
#include <stdlib.h>
 
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *head;

void initialize(){
    head = NULL;
}

/* 
Given a Inserts a node in front of a singly linked list. 
*/
void insert(int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = head;
    /* make new node as new head of linked list */
    head = newNode;
    printf("Inserted Element : %d\n", num);
}

/* Reverses a given Linked List, and return 
the head pointer of reversed linked list */
struct node* reverseLinkedList(struct node *head) {
    struct node *previous, *current, *next;
    previous = NULL;
    current = head;

    while (current != NULL) {
        next  = current->next;  
        current->next = previous;   
        previous = current;
        current = next;
    }
    return previous;
}

/*
Prints a linked list from head node till tail node 
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
 
int main() {
    initialize();
    /* Creating a linked List*/
    insert(8);  
    insert(3); 
    insert(2); 
    insert(7);
    insert(9);
    
    printf("\nLinked List\n");
    printLinkedList(head);
    
    /* Reverse Linked List */
    head = reverseLinkedList(head);
    printf("\nReversed Linked List\n");
    printLinkedList(head);
    
    return 0;
}
Output
Inserted Element : 8
Inserted Element : 3
Inserted Element : 2
Inserted Element : 7
Inserted Element : 9

Linked List
8-->3-->2-->7-->9
Reversed Linked List
9-->7-->2-->3-->8

Reverse a Linked List using Recursion

Algorithm to reverse a linked list using iteration
Let "reverse(struct node* nodePtr)" be the recursive function which reverses a linked list whose head node is pointed by nodePtr.
  • Recursion termination condition : if(nodePtr->next == NULL) set head = nodePtr;
  • Recursively call "reverse" function to reverse sub list reverse(nodePtr->next);
  • Add nodePtr to the end of the reversed Llinked List. Set nodePtr->next->next = nodePtr;
  • Now, nodePtr is the tail node of reversed linked list. Set nodePtr->next = NULL.
#include <stdio.h>
#include <stdlib.h>
 
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *head;

void initialize(){
    head = NULL;
}

/* 
Given a Inserts a node in front of a singly linked list. 
*/
void insert(int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = head;
    /* make new node as new head of linked list */
    head = newNode;
    printf("Inserted Element : %d\n", num);
}

/* Reverses a Linked List using recursion */
void reverse(struct node* nodePtr) {
      
    /* empty list */
    if (nodePtr == NULL)
       return;   
    /* Last node (tail node)*/
    if(nodePtr->next == NULL){
        head = nodePtr;
        return;   
    }
 
    /* reverse the rest of list and put the first element at the end */
    reverse(nodePtr->next);
    nodePtr->next->next = nodePtr;  
    nodePtr->next = NULL;               
}

/*
Prints a linked list from head node till tail node 
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
 
int main() {
    initialize();
    /* Creating a linked List*/
    insert(1);  
    insert(2); 
    insert(3); 
    insert(4);
    insert(5);
    
    printf("\nLinked List\n");
    printLinkedList(head);
    
    /* Reverse Linked List */
    reverse(head);
    printf("\nReversed Linked List\n");
    printLinkedList(head);
    
    return 0;
}
Output
Inserted Element : 1
Inserted Element : 2
Inserted Element : 3
Inserted Element : 4
Inserted Element : 5

Linked List
5-->4-->3-->2-->1
Reversed Linked List
1-->2-->3-->4-->5
Posted by
Labels: