Swap nodes in a linked list without swapping data O(n)
What I have done is take three pointers to for each element that has to be swapped. And using that three pointers I swap the nodes in the linked list.Will work fine for if we will not take first and last element to be swapped.Will update for the all cases soon...
#include<stdio.h>
#include<stdlib.h>
struct node
{
char data;
struct node *next;
}*head;
void insert(int num)
{
struct node* temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;
temp->next=NULL;
if(head==NULL)
{
head=temp;
}
else
{
struct node* temp1=head;
while(temp1->next!=NULL)
{
temp1=temp1->next;
}
temp1->next=temp;
}
}
void display()
{
struct node *temp2;
temp2=head;
while(temp2!=NULL)
{
printf("%d ",temp2->data);
temp2=temp2->next;
}
}
void swapping_the_element(int n1,int n2)
{
struct node* temp1=head;
struct node* temp2=head;
struct node* prev1;
struct node* prev2;
struct node* next1;
struct node* next2;
while(temp1->data!=n1)
{
prev1=temp1;
temp1=temp1->next;
next1=temp1->next;
}
while(temp2->data!=n2)
{
prev2=temp2;
temp2=temp2->next;
next2=temp2->next;
}
prev1->next=temp2;
temp2->next=next1;
prev2->next=temp1;
temp1->next=next2;
}
int main()
{
int i,num;
int pos;
int n1,n2;
struct node *n;
head=NULL;
while(1)
{
printf("\nList Operations\n");
printf("===============\n");
printf("1.Insert\n");
printf("2.Display\n");
printf("3.swapping the elements of the liked list\n");
printf("4.Exit\n");
printf("Enter your choice : ");
if(scanf("%d",&i)<=0){
printf("Enter only an Integer\n");
exit(0);
} else {
switch(i)
{
case 1: printf("Enter the number to insert : ");
scanf("%d",&num);
insert(num);
break;
case 2: if(head==NULL)
{
printf("List is Empty\n");
}
else
{
printf("Element(s) in the list are : ");
}
display(n);
break;
case 3:
if(head==NULL)
{
printf("List is Empty\n");
}
else
{
printf("Enter the numbers to be swapped\n");
scanf("%d %d",&n1,&n2);
printf("Swapping the elements of the liked list\n");
swapping_the_element(n1,n2);
}
break;
case 4:
return 0;
default: printf("Invalid option\n");
}
}
}
}
No comments:
Post a Comment