Thursday, November 22, 2012

Reverse the adjacent nodes in a linked list

Reverse the adjacent nodes of a linked list as described below in the sample input and output:
Input 1: 1->2->3->4->5
Output1: 2->1->4->3->5
Input2: 1->2->3->4->5->6
Output2: 2->1->4->3->6->5

#include<iostream>
#include<stdlib.h>
using namespace std;

struct node
{
int data;
struct node* next;
};

struct node* createlist(int length)
{
struct node *root=NULL,*end=NULL;
for(int i=1;i<=length;i++)
{
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data=i;
new_node->next=NULL;
if(i==1)
{
root=new_node;
end=root;
}
else
{
end->next=new_node;
end=new_node;
}
}
return root;
}
struct node* reverseadjacent(struct node* root)
{
int length=0;
struct node *temp=root;
while(temp!=NULL)
{
length++;
temp=temp->next;
}
if(length<2)
{
return root;
}
struct node *first=root,*sec=first->next,*third=sec->next;
root=first->next;
if(length==2)
{
sec->next=first;
first->next=NULL;
}
else if(length%2==0)
{
while(third!=NULL)
{
first->next=third->next;
sec->next=first;
first=third;
sec=third->next;
third=sec->next;
}
sec->next=first;
first->next=NULL;
}
else
{
while(third->next!=NULL)
{
first->next=third->next;
sec->next=first;
first=third;
sec=third->next;
third=sec->next;
}
sec->next=first;
first->next=third;
}
return root;
}
void printlist(struct node* root)
{
struct node* temp=root;
while(temp!=NULL)
{
cout<<temp->data<<"->";
temp=temp->next;
}
cout<<endl;
}
int main()
{
struct node* root=createlist(5);
cout<<"The given list\n";
printlist(root);
struct node* new_root=reverseadjacent(root);
cout<<"The new list\n";
printlist(new_root);
}

No comments:

Post a Comment