Reversing a singly linked list
Reverse() function reverses the linked list i.e the last node becomes the first one, the second last node becomes the second one and so on.
Summary of Reverse()
To reverse the linked list, 2 pointers are required.
First one is curr and is initialized by the head of the linked list:
Node*curr=head;
and the second one is next which is initialized by NULL:
Node*next=NULL;
First, the curr->link will be stored in the next pointer
Second, the next->link will be assigned to the curr->link
Third, the head will be assigned to the next->link
And at the last the next is assigned to the head, and this process continues till the end of the linked list.
while(curr->link!=NULL)
{
next=curr->link;
curr->link=next->link;
next->link=head;
head=next;
}
Code
#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;
struct Node
{
public:
int data;
Node*link;
Node();
};
Node::Node()
{
data=0;
link=NULL;
}
class LinkList
{
public:
Node*head;
LinkList();
void AddNodeAtEnd(int);
void DisplayWhole();
void Reverse();
};
LinkList::LinkList()
{
head=NULL;
}
void LinkList::AddNodeAtEnd(int _data)
{
Node*node=new Node();
node->data=_data;
node->link=NULL;
if(head==NULL)
head=node;
else
{
Node*tptr=head;
while(tptr->link!=NULL)
tptr=tptr->link;
tptr->link=node;
}
}
void LinkList::DisplayWhole()
{
Node*temp=head;
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->link;
}
}
void LinkList::Reverse()
{
Node*curr=head;
Node*next=NULL;
while(curr->link!=NULL)
{
next=curr->link;
curr->link=next->link;
next->link=head;
head=next;
}
}
int main()
{
LinkList l;
// Adding first element to the linked list
l.AddNodeAtEnd(10);
// Adding second element to the linked list
l.AddNodeAtEnd(20);
// Adding third element to the linked list
l.AddNodeAtEnd(30);
// Adding fourth element to the linked list
l.AddNodeAtEnd(40);
// Adding fifth element to the linked list
l.AddNodeAtEnd(40);
// Adding sixth element to the linked list
l.AddNodeAtEnd(50);
// Adding seventh element to the linked list
l.AddNodeAtEnd(60);
// Adding eighth element to the linked list
l.AddNodeAtEnd(70);
// Adding ninth element to the linked list
l.AddNodeAtEnd(80);
// Displaying all nodes in the linked list
cout<<"Linked list before Reversal : "<<endl;
l.DisplayWhole();
cout<<endl<<endl;
l.Reverse();
// Displaying all nodes in the linked list
cout<<"Linked list after Reversal : "<<endl;
l.DisplayWhole();
cout<<endl<<endl;
_getche();
return 0;
}
Output
Linked list before Reversal :
10 20 30 40 40 50 60 70 80
Linked list after Reversal :
80 70 60 50 40 40 30 20 10
0 comments:
Post a Comment