#include <stdio.h>

#include <stdlib.h>

typedef struct Node

{

char c;

struct Node *next;

}Node;

typedef Node *slist;

slist reverse(slist s)

{

if(s->next == NULL)

return s;

Node *ret = reverse(s->next);

s->next->next = s;

s->next = NULL;

return ret;

}

Node *makeNode(char c)

{

Node * tmp = calloc(sizeof(Node), 1);

tmp->c = c;

return tmp;

}

void print(slist s)

{

if(s == NULL)

return;

printf("%c", s->c);

print(s->next);

}

/*

Divede the list into two halves using slowfast algo..

reverse the second part

now compare both the parts

incase odd number of elements in the list, second part is the big one

*/

int palindrome(slist s)

{

Node *prevslow = NULL;

Node *slow = s;

Node *fast = s;

//divide into two parts

while(fast)

{

if(fast->next)

fast = fast->next->next;

else

break;

prevslow = slow;

slow = slow->next;

}

prevslow->next = NULL;

//reverse the second part

fast = reverse(slow);

//to retain the list

slow = fast;

//compare two parts

while(s && fast->c == s->c)

{

fast = fast->next;

s = s->next;

}

if((fast == NULL || fast->next == NULL) && s == NULL)

printf("Plaindrome\n");

else

printf("Not Plaindrome\n");

//retain the list back

prevslow->next = reverse(slow);

}

int main()

{

slist s = makeNode('s');

s->next = makeNode('a');

s->next->next = makeNode('a');

s->next->next->next = makeNode('a');

s->next->next->next->next = makeNode('s');

palindrome(s);

return 0;

}

Advertisements