Monday, 18 February 2013

Some other operations over circular linked list...:)
1.Reversal of circular linked list

void reverse(struct node **ps)
{
struct node *temp,*temp1,*temp2;
temp1=*ps;
temp=*ps;
while(temp1->next!=*ps)
temp1=temp1->next;
do
{
temp2=temp1;
temp1=temp;
temp=temp->next;
temp1->next=temp2;
}while(temp!=*ps);
*ps=temp1;
}

2.Appending elements in sorted order

void append(struct node **ps,int x)
{
struct node *temp,*temp1,*prev;
temp1=(struct node *)malloc(sizeof(struct node));
temp1->data=x;
if(*ps==NULL)
{
*ps=temp1;
(*ps)->next=*ps;
return;
}
temp=*ps;
if((*ps)->data>x)
{
temp1->next=*ps;
while(temp->next!=*ps)
temp=temp->next;
temp->next=temp1;
*ps=temp1;
return;
}
while(temp->next!=*ps && temp->data<x)
{
prev=temp;
temp=temp->next;
}
if(temp->data<x)
{
temp->next=temp1;
temp1->next=*ps;
}
else
{
prev->next=temp1;
temp1->next=temp;
}
}

3.Leaving the k locations and deleting next k locations repeatedly.
Note-Here only one node will remain at last whose data value will be returned.

int del(struct node **ps, int k)
{
struct node *temp,*temp1,*prev;
int i,j;
temp=*ps;
prev=temp;
while((*ps)->next!=*ps)
{
for(i=0;i<k;i++)
{
prev=temp;
temp=temp->next;
}
for(j=0;j<k;j++)
{
if((*ps)->next==*ps)
break;
temp1=temp;
temp=temp->next;
prev->next=temp1->next;
if(temp1==*ps)
*ps=temp1->next;
free(temp1);
}
if(j!=k)
break;
}
return ((*ps)->data);
}

4.Josephus problem where we have to delete every xth node

int josephus(struct node **ps,int x)
{
struct node *temp,*temp1,*prev;
temp=*ps;
int i;
while((*ps)->next!=*ps)
{
i=0;
while(i!=x)
{
prev=temp;
temp=temp->next;
i++;
}
temp1=temp;
prev->next=temp->next;
temp=temp->next;
if(temp1==*ps)
*ps=temp1->next;
free(temp1);
}
return (*ps)->data;
}



No comments:

Post a Comment