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