# Is Singly Linked List a Palindrome ??

230 views

WAP to Check whether a Singly Linked List is a Palindrome ??
time complexity should be O(n) ??

posted Nov 4, 2013

+1 vote

Using recursion, this can be implemented in O(n).

This is  my sample program:
struct node {
char data;
} *start, *last;

char value[10];
int i=0;

struct node *temp, *iterate;
iterate=start;
temp= (struct node *)malloc(sizeof(struct node));
temp->data=insert;

if(start==NULL){
start=temp;
last=temp;
}
else{
}
last=temp;
}
}

void checkpalindrom(struct node *tansverse){

if(tansverse == NULL){
return;
}

else {

value[i]=tansverse->data;
printf(" %c \n", value[i] );
i++;
}

if(tansverse->data != value[--i]){
printf(" Not matched ");
return;
}

}

int main()
{
checkpalindrom(start);
return 0;
}
Sorry to mention about O(n) space complexity ... I think this is same as using  the  stack
But this seems to be better then stack as that would require the o(n) space complexity. But this would be require a global variable (thats too an array)
Not  required  to use array as  global, if required  u can declare this array locally and  pass to the recursive function( may use  pointer for ref to this array).

A simple solution is to use a stack of list nodes. This mainly involves three steps.
1) Traverse the given list from head to tail and push every visited node to stack.
2) Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node.
3) If all nodes matched, then return true, else false.

Time complexity of above method is O(n), but it requires O(n) extra space. Following methods solve this with constant extra space.