×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

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 


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.