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 1
Initialize:
cur =1, prev=NULL, next=NULL

in iteration 1:
next=2
cur->next=NULL
prev=1
cur=2
thus reversed part: 1->NULL

in iteration 2:
next=3
cur->next=1
prev=2
cur=3
thus reversed part: 2->1->NULL

in iteration 3:
next=4
cur->next=2
prev=3
cur=4
thus reversed part: 3->2->1->NULL

in iteration 4:
next=5
cur->next=3
prev=4
cur=5
thus reversed part: 4->3->2->1->NULL

in 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