Tuesday, October 20, 2015

Rearrange a given linked list in-place

#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;
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[]={2,23,4,15,6,17,8,'\0'};
int n=7;
node *t=NULL;
for(int i=0;i<n;i++)
{
create(t,a1[i]);
}
print(t);
node *a[100];
node *t1=t;
int i=0;
node *t2=t;

while(t2&&t2->next&&t2->next!=NULL)
{
t1=t1->next;
t2=t2->next->next;
}
if(t2!=NULL)
t1=t1->next;
t2=t;
while(t2->next!=t1)
t2=t2->next;
t2->next=NULL;
print(t);cout<<endl;
print(t1);
rev(t1);
t=merge(t,t1);
print(t);
return 0;
}

No comments:

Post a Comment

Contributors

Translate