An efficient way to write a program for checking whether it is palindrome or not......Here i am using XOR linked list for this purpose.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h> // For supporting uintptr_t
typedef struct Linkedlist // structure creation
{
int data;
struct Linkedlist *next;
}xorll;
xorll *Insertnode(xorll *prev,xorll *cur,int data) // Node will be created here
{ xorll *new;
new=(xorll*)malloc(sizeof(xorll));
new->data=data;
new->next=prev;
if(!cur); // if first node is null
else if(!prev) // if it is second node
{
cur->next=(uintptr_t)prev^(uintptr_t)new;
new->next=cur;
}
else // for general cases (more than two nodes)
{
prev->next=(uintptr_t)prev->next^(uintptr_t)new;
}
return new;
}
void Traverse(xorll *ptr) // For traversing the List .....Added for clear picture
{
xorll *prev=NULL,*temp;
if(!ptr) {printf("Nothing to print there\n");return;} // if first node is null
do // for general cases
{ temp=ptr;
printf("%c ",ptr->data); // I have assumed character string as input
ptr=(uintptr_t)prev^(uintptr_t)ptr->next;
prev=temp;
}while(ptr!=NULL); // if it is last node get out from here you are done
}
void Palindrome(xorll *headptr,xorll *tailptr) // The actual function for checking palindrome
{
xorll *headprev=NULL,*tailprev=NULL,*temph,*tempt;
if(!headptr) {printf("Empty list\n");return;} // if any of the means no List exists
//Now we have to check for lower and upper case letters
while(headptr->data==tailptr->data||headptr->data+32==tailptr->data||headptr->data==tailptr->data+32)
{
temph=headptr;
tempt=tailptr;
if(headptr==tailptr)
{
printf("palindrome\n");
return;
}
headptr=((uintptr_t)headprev^(uintptr_t)headptr->next);
if(headptr==tailptr)
{
printf("Palindrome\n");
return;
}
tailptr=(uintptr_t)tailprev^(uintptr_t)tailptr->next;
headprev=temph;
tailprev=tempt;
}
printf("Not a palindrom\n");
}
int main(int argc, char ** argv)
{
xorll *Head,*Tail;
Head=Tail=NULL;
int i=0,data;
while(i<5) // Link creation, for 5 characters you can make it large
{
scanf("%c",&data);
if(i==0) // for first node
Head=Tail=Insertnode(Head,Tail,data);
else if(i==1) // for second node
Tail=Insertnode(NULL,Tail,data);
else // for general case
Tail=Insertnode(Tail,Tail,data);
i++;
}
printf("\nFrom front of the list\n");
Traverse(Head);
printf("\nFrom Back of the list\n");
Traverse(Tail);
printf("\n\n");
Palindrome(Head,Tail);
return 0;
}
