• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2022
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

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

Aniruddha Chaudhari/25665/2
C / C++Code

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?

cppLinked List
Aniruddha Chaudhari
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Comments

  • Reply
    Natalie
    April 10, 2016 at 6:38 pm

    Thanks Aniruddha for posting this article and code for Linked List.

    • Reply
      Aniruddha Chaudhari
      February 4, 2019 at 10:02 pm

      You’re welcome and I am glad as you like it.

Leave a Reply Cancel reply

C Programming

  1. C- Introduction
  2. C- Compile & Execute Program
  3. C- Data Types
  4. C- if-else statement
  5. C- While, do-while, for loop
  6. C- Array
  7. C- Function (Types/Call)
  8. C- strlen() vs sizeof()
  9. C- Nested Switch Statement
  10. C- Recursion
  11. C- Dynamic Programming
  12. C- Storage Classes
  13. C- Creating Header File
  14. C- Null Pointer
  15. C- Stack and Queue
  16. C- Implement Stack using Array
  17. C- Implement Linked List in C
  18. C- File Handling
  19. C- Makefile Tutorial

Object Oriented Concepts in C++

  • C++: C vs OOPs Language
  • C++: Introduction to OOPs Concepts
  • C++: Inheritance

Sorting Algorithms

  • Different Types of Sorting Algo
  • Selection Sort
  • Bubble Sort
  • Quick Sort

Programming for Practice

  1. Online C/C++ Compiler

String Handling:

  1. Remove White Spaces from String
  2. Implement strstr Function in C
  3. Convert String to Int – atoi()
  4. Check if String is Palindrome
  5. Check if Two Strings are Anagram
  6. Split String in using strtok_r()
  7. Undefined reference to strrev

Array:

  1. Check if Array is Sorted

Bit Manipulation:

  1. Count Number of 1’s in Binary

Linked List:

  1. Reverse a Linked List Elements

Number System:

  1. Program to Find 2’s Complement
  2. Convert Decimal to Binary in C

Tricky Questions:

  1. Add Two Numbers without Operator
  2. Find Next Greater Number
  3. Swap values without temp variable
  4. Print 1 to 100 without Loop

Interview Coding Questions

  • 50+ Interview Coding Questions

© 2022 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard