Tuesday, October 20, 2015

Sort a linked list that is sorted alternating ascending and descending orders

Input List:   10->40->53->30->67->12->89->NULL
Output List:  10->12->30->43->53->67->89->NULL

#include <iostream>
using namespace std;
struct node {
int data;
node *next;

};

void print(node *t)
{

while(t!=NULL)
{
cout<<t->data<<" ";
t=t->next;
}
cout<<endl;
}
void rev(node *&t)
{
node *temp=NULL;
node *next;
node *cur=t;
while(t!=NULL)
{
next=t->next;
t->next=temp;
temp=t;
t=next;
}
t=temp;
}
void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->next=NULL;

}
else
{
create(t->next,a);
}
}
node *merge(node *t1,node *t2)
{
node *t=t1;
node *head=t;
t1=t1->next;
while(t1&&t2)
{

t->next=t2;
t=t->next;
t2=t2->next;
if(t1&&t2&&t2->data>t1->data)
{
node *temp=t1;
t1=t2;
t2=temp;
}
}
if(t1!=NULL)
t->next=t1;
else if(t2!=NULL)
t->next=t2;
return  head;
}
int main()
{
int a1[]={10 ,40 ,53 ,30 ,67, 12, 89,'\0'};
int n=7;
node *t=NULL;
for(int i=0;i<n;i++)
{
create(t,a1[i]);
}
print(t);
node *t1=t;
node *h1=NULL;
node *h2=NULL;
while(t1!=NULL&&t1->next!=NULL)
{
create(h1,t1->data);
t1=t1->next;
create(h2,t1->data);
t1=t1->next;
}
if(t1!=NULL)
create(h1,t1->data);
print(h1);

//print(h2);
rev(h2);
print(h2);
t=merge(h1,h2);
print(t);
return 0;
}

No comments:

Post a Comment

Contributors

Translate