Given a singly linked list, swap kth node from beginning with kth node from end. Swapping of data is not allowed, only pointers should be changed. This requirement may be logical in many situations where the linked list data part is huge (For example student details line Name, RollNo, Address, ..etc). The pointers are always fixed (4 bytes for most of the compilers).
problem defination available at : swap-kth-node-from-beginning-with-kth-node-from-end-in-a-linked-list
code :
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node * link;
};
struct node *createNode(int data)
{
struct node *p=NULL;
p=(struct node *)malloc(sizeof(struct node));
p->data=data;
p->link=NULL;
return p;
}
struct node *traverseTillEnd(struct node *head) //will return the pointer to the last node.
{
struct node *p=head;
if(head==NULL)
{
return NULL;
}
else
{
while((p->link)!=NULL)
{
p=p->link;
}
return p;
}
}
struct node *insert(struct node * head,int data)
{
struct node *p=NULL;
if(head==NULL)
{
head=createNode(data);
return head;
}
else
{
// traverse the node till end.
p=traverseTillEnd(head);
p->link=createNode(data);
return head;
}
}
int count(struct node *head) // return the number of nodes the list have.
{
int i=0;
if(head==NULL)
{
return 0;
}
else
{
while(head!=NULL)
{
i++;
head=head->link;
}
return i;
}
}
void printList(struct node *head)
{
while(head!=NULL)
{
printf("-%d-",(head->data));
head=head->link;
}
printf("\n");
}
struct node * swap(struct node *head,int k) // takes head of the linked list and k value as argument.
{
struct node *temp1=NULL,*temp2=NULL,*tempp1=NULL,*tempp2=NULL;
struct node *x=NULL,*y=NULL;
struct node * temp=NULL;
int total=count(head);
// find the kth node from starting.
if(k>total)
{
return head; // I can not return NULL because , it will affect my original linked list , as I am storing return value of this function to the head of the list.
}
if(k==0)
{
return head; // no change...
}
if(k==0)
{
return head; // no change...
}
x=head;
while(k!=1)
{
temp1=x;
x=x->link;
k--;
}
tempp1=x->link;
// at this point x is pointing to the kth location form starting node of the list.
// now I have to find the kth node form last.
y=head;
temp=x;
while((temp->link)!=NULL)
{
temp2=y;
y=y->link;
temp=temp->link;
}
tempp2=y->link;
// at this point y is pointing to the kth location form last node of the list.
// test all the variables..
/*
printf("\n%d\n",temp1->data);
printf("\n%d\n",x->data);
printf("\n%d\n",tempp1->data);
printf("\n%d\n",temp2->data);
printf("\n%d\n",y->data);
printf("\n%d\n",tempp2->data);
*/
// let swapping process starts
if((x->link)==y) // y is next to x
{
temp1->link=y;
x->link=tempp2;
y->link=x;
}
else if((y->link)==x) // x is next to y
{
temp2->link=x;
x->link=y;
y->link=temp1;
}
else if(x==y)
{
// then why to swap ?
}
else if(x==head) // it is possible that x is pointing to head node , then its time to change my head node.
{
temp2->link=x;
x->link=NULL;
y->link=tempp1;
head=y;
}
else if(y==head) // it is possible that y is pointing to head node , then its time to change my head node.
{
temp1->link=y;
y->link=NULL;
x->link=tempp2;
head=x;
}
else // normal cases.
{
y->link=x->link;
temp1->link=y;
x->link=tempp2;
temp2->link=x;
}
return head;
}
int main(int argc,char *argv[])
{
int i=0;
int val[argc];
struct node *head=NULL;
printf("%d number of argument provided.\n",(argc-1));
for(i=1;i<argc;i++)
{
val[i]=atoi(argv[i]); // convert Ascci to Int
head=insert(head,val[i]);
}
printList(head);
head=swap(head,1);
printList(head);
return 0;
}
// compile : gcc -c swap.c
// link : gcc -o swap swap.o
// execute : ./swap 10 15 20 25 26 28 29 35 40 42 44 45 48
// all comments are invited , please let me know if code fails for particular case.
No comments:
Post a Comment