Write C/C++ Program to Reverse a Linked List without Recursion?

The linked list is the crucial data structure that contains a list of the nodes. Each node has a data variable to store data and a node pointer to point next node in the linked list.

Prerequisite: How to create Linked List in C/C++?

In the previous post, we have seen the implementation of the Linked List in C. Go through it.

In this post, we see how to reverse the elements of the linked list using three-pointers in C/C++. We have also solved the same problem in Java as well.

Reverse Singly Linked List Implementation (Logic):

Basically, there are two approaches to reverse the linked list.

1. With Recursion
2. Without Recursion

In this programming tutorial, we are reversing linked list with and without recursion.

1. Print Linked List in Reverse Order using Recursion in C

Prerequisite: Recursion in C Explained with Example

Algorithm: Here we need head recursion. It includes two steps are as follows

• call recursive function for next node (p->pLink)
• print data at node (p->nData)

Difficulty Level: Moderate if you are familiar with Linked List and Recursion.

C Program to Print Linked List in Reversed Order using Recursion

#include<stdio.h>

//Structure for Linked List Node
struct node
{
  int nData;
  struct node* pLink;
};
 
//Function to display Linked List 
// in reverse order using recursion
void displayLLReverse(struct node* p)
{
  //base condition for recursion
  if(!p)
    return;
  else
  {
    //call recursively
    displayLLReverse(p->pLink);
    printf("%d ", p->nData);
  }
}
 
int main()
{
  struct node* pNode1= NULL;
  struct node* pNode2= NULL;
  struct node* pNode3= NULL;
 
  //create node and assign data value
  pNode1 = (struct node *)malloc(sizeof(struct node *));
  pNode1->nData =10;
 
  pNode2 = (struct node *)malloc(sizeof(struct node *));
  pNode2->=20;
 
  pNode3 = (struct node *)malloc(sizeof(struct node *));
  pNode3->nData =30;
 
  //connecting nodes
  pNode1->pLink = pNode2;
  pNode2->pLink = pNode3;
  pNode3->pLink = NULL;
 
  //Display Linked List in reverse order using recursion 
  //if first node is not null
  if(pNode1)
  displayLLReverse(pNode1);
}

Elements in the Linked List are 10, 20, 30. After running this program element will print Linked List in reverse order as 30 20 10.

Time Complexity:

Time Complexity for this program will be <strong>O(n)</strong> as we are calling recursion at once for each node.

2. Reverse the Linked List without Recursion in C/C++

The original Linked list will be passed to the function to reverse. It will exchange the links between every two consecutive nodes.

This reverse a Linked List function will maintain two lists: one linked list contents reverse elements and second linked list contents remaining elements that need to be reversed.

Logically reverse a linked list function seems kinda difficult, but if you see the code for it, it is so simple and easy to understand.

C Program to Reverse a Linked List Without Recursion (C/C++ Code)

Also added comments in the code where it is required so that it will be easy to understand.

#include<stdio.h>
 
struct node
{
  int nData;
  struct node* pNext;
};
 
struct node* insertNodeAtEnd(struct node*p , int n)
{
  struct node *pRoot = p;
  struct node* pTemp = (struct node*)malloc(sizeof(struct node*));
  pTemp->nData = n;
  pTemp->pNext = NULL;
 
  if(!pRoot)
    return pTemp;
  else
  {
    struct node* pPar = p;
    while(p->pNext)
    {
      p=p->pNext;
    }
    p->pNext =pTemp;
    return pRoot;
  }
}
 
void displayLL(struct node* p)
{
  if(!p)
    printf("LinkList empty");
  else
  {
    do
    {
      printf(" %d", p->nData);
      p=p->pNext;
    }
    while(p);
  }
}
 
/* Function to reverse a Linked List elements
using 3 pointers
q = original Linked list
r = pointer to the reversed linked list
s = pointer to the last element of reversed linked list
*/
struct node * reverseLL(struct node *q)
{
  struct node*r =NULL;
  struct node*s =NULL;
 
  while(q)
  {
    s=r;
    r=q;
    q=q->pNext;
    r->pNext=s;
  }
  return r;
}
 
int main()
{
  struct node *start =NULL;
  // add elements in Linked List
  start = insertNodeAtEnd(start,10);
  start = insertNodeAtEnd(start,20);
  start = insertNodeAtEnd(start,30);
  start = insertNodeAtEnd(start,40);
  // display original Linked List elements
  printf("\nDisplay Linked List: ");
  displayLL(start);
  //Reverse the Linked List
  start = reverseLL(start);
  // display reversed Linked List elements
  printf("\nDisplay Reverse Linked List: ");
  displayLL(start);
}

Output :

Display Linked List: 10 20 30 40
Display Reversed Linked List:: 40 30 20 10

Complexity for Program to Find the Reverse Linked List

The difficulty level of this program is medium. If you are new to the C programming and C structure, you may find it a little difficult.

We are traversing each element at one time, so its complexity is O(n). so the Time Complexity is O(n).

What’s Next?

Reverse a Linked list is one of the important questions to be asked in many placement interviews. I was asked to write code for this program in the IBM ISDL interview (On-campus NIT Trichy).

Practice solving more coding questions. These questions are asked in many interview rounds.

If you have any doubt for C Program to Reverse a Linked List without recursion, kindly comment below. I will try my best to reply as soon as possible.

Next Challenge: How to reverse the second half of the given linked list in C?