Home » Interview coding problems/challenges

# Reverse a single linked list

In this article, we are going to see **how to reverse a single linked list**? This problem has come to coding round of Amazon, Microsoft.

Submitted by Radib Kar, on December 02, 2018

**Problem statement:** Given a linked list reverse it without using any additional space (In O(1) space complexity).

**Solution:**

**Reversing a single linked list** is about reversing the linking direction. We can solve the above problem by following steps:

**1. Building the linked list**

Firstly, we build the linked list by inserting each node at the beginning. For detailed analysis of how to build a linked list using insertion at beginning, kindly go through this full article: **Single linked list insertion**

**2. Function to reverse the link list**

As told previously, the basic idea to reverse a linked list is to reverse the direction of linking. This concept can be implemented without using any additional space. We need three pointers *prev, *cur, *next to implement the function. These variables are named accordingly to indicate their serving part in the function.

*prev - to store the previous node which will become ultimately the next node after reversal for current node

*cur - to store the current node

*next - to store the next node which will become current node in the next iteration.

Initialize *prev & *next to NULL, *cur to head

while(cur!=NULL) Set *nextto cur->next Set cur->nextto *prev Set *prev to *cur Set *cur to *next End While loop Set head to *prev

**3. Print the reversed linked list**

**Example: **

Let the linked list be 1->2->3->4->5->NULL (for simplicity in understanding representing pointer to node by node value) Head is 1Initialize:cur =1, prev=NULL, next=NULLin iteration 1:next=2 cur->next=NULL prev=1 cur=2 thus reversed part: 1->NULLin iteration 2:next=3 cur->next=1 prev=2 cur=3 thus reversed part: 2->1->NULLin iteration 3:next=4 cur->next=2 prev=3 cur=4 thus reversed part: 3->2->1->NULLin iteration 4:next=5 cur->next=3 prev=4 cur=5 thus reversed part: 4->3->2->1->NULLin iteration 5:next=NULL cur->next=4 prev=5 cur=NULL thus reversed part: 5->4->3->2->1->NULL iteration ends at cur is NULL linked list reversed, head at 5

## C++ program to reverse a single linked list

#include<bits/stdc++.h> using namespace std; class node{ public: int data; // data field node *next; }; node* reverse(node* head){ node *next=NULL,*cur=head,*prev=NULL; //initialize the pointers while(cur!=NULL){//loop till the end of linked list next=cur->next;//next = cur->next to store the rest of the list; cur->next=prev;//change the direction of linked list prev=cur; //update prev cur=next; //update cur } head=prev; //update head return head; //return head } void traverse(node* head){ node* current=head; // current node set to head int count=0; // to count total no of nodes printf("\ntraversing the list\n"); while(current!=NULL){ //traverse until current node isn't NULL count++; //increase node count printf("%d ",current->data); current=current->next; // go to next node } printf("\ntotal no of nodes : %d\n",count); } node* creatnode(int d){ node* temp=(node*)malloc(sizeof(node)); temp->data=d; temp->next=NULL; return temp; } int main(){ printf("creating the linked list by inserting new nodes at the begining\n"); printf("enter 0 to stop building the list, else enter any integer\n"); int k,count=1,x; node* curr; scanf("%d",&k); node* head=creatnode(k); //buliding list, first node scanf("%d",&k); //inserting at begining//// while(k){ curr=creatnode(k); curr->next=head; //inserting each new node at the begining head=curr; scanf("%d",&k); } traverse(head); // displaying the list cout<<"reversing the list............"<<endl; head=reverse(head);// reverse the linked list traverse(head);//display reversed linked list return 0; }

**Output**

creating the linked list by inserting new nodes at the begining enter 0 to stop building the list, else enter any integer 6 7 8 9 4 3 3 1 0 traversing the list 1 3 3 4 9 8 7 6 total no of nodes : 8 reversing the list............ traversing the list 6 7 8 9 4 3 3 1 total no of nodes : 8

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.