   Is Singly Linked List a Palindrome ??

262 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). answer Nov 5, 2013
This is  my sample program:
struct node {
char data;
} *start, *last;

char value;
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{
while (iterate->link != NULL) {
}
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. answer Nov 5, 2013
I think it can be done in n/2 space with a little complexity.
Assuming l is length of linklist (if not known it would require another iteration over linklist). Start iteration over linklist and push elements in stack till count reaches to l/2. On this point If l is odd skip next linklist element else start popping elements from stack and match with linklist. It does not match it's not a palindrome else it is.
+1
Make sense but would require more code to be written as it is difficult to find out the half of LinkList.
Similar Questions