Goal: Program to rotate a Linked List Counter clock wise.
Method-used: No specific Method.Logic is illustrated Below.
Description:-
This program is quite difficult to understand that's why we are taking a example :
Suppose we have a linked list 1->2->3->4->5 and we have to rotate it by 2 nodes then resultant linked list will be 3->4->5->1->2.
For doing rotation we assign the original head to node 3 and next-pointer of node 5 to our original head. For making node 2 as last node of linked list we assign its pointer to NULL.
Program:-
#include<iostream>
#include<conio.h>
using namespace std;
struct node {
int info;
node *next;
};
node *head1;
node *create()
{
int i,n,data,;
node *p1,*temp1;
head1=NULL;
temp1=NULL;
cout<<"\n\tHow many Elements you want to enter:\n";
cout<<"\t";
cin>>n;
cout<<"\n\t Enter Elemnts:\n";
for(i=0;i<n;i++)
{
cout<<"\t";
cin>>data;
if(head1==NULL)
{
p1=new node;
p1->info=data;
p1->next=NULL;
head1=p1;
temp1=p1;
}
else
{
p1=new node;
p1->info=data;
p1->next=NULL;
temp1->next=p1;
temp1=p1;
}
}
p1=head1;
return p1;
}
void display(node *p2)
{
cout<<"\t";
cout<<"Displaying:--\n";
if(p2==NULL)
cout<<"NULL";
while(p2)
{
cout<<"\t";
cout<<p2->info<<"\t";
p2=p2->next;
}
}
node * rotate(node *p2)
{
int m,k,count=1;
node *temp;
p2=head1;
cout<<"\n\t";
cout<<"Enter the position of node(For rotation):\n";
cout<<"\t";
cin>>m;
while(count<m & p2->next!=NULL)
{
count++;
p2=p2->next;
}
if(p2==NULL )
{
p2=head1;
return p2;
}
temp=p2;
while(p2->next!=NULL)
{
p2=p2->next;
}
p2->next=head1;
head1=temp->next;
temp->next=NULL;
p2=head1;
return p2;
}
int main()
{
node *p1,*head,*temp;
head=NULL;
temp=NULL;
p1=create();
display(p1);
p1=rotate(p1);
cout<<"\n\t After Rotation:-";
display(p1);
getch();
}
Output:
Complexity:-
Complexity of above program is O(n). Because it checks all the nodes only one time.
If you want to share more information about topic discussed above or find anything incorrect Please do comments.
0 comments:
Post a Comment