top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Is Singly Linked List a Palindrome ??

+5 votes
902 views

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

posted Nov 4, 2013 by Mona Sharma

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

+1 vote

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

answer Nov 5, 2013 by Amit Kumar
This is  my sample program:
struct node {
char data;
struct node *link;
} *start, *last;

char value[10];
int i=0;

void addNode(char insert){
struct node *temp, *iterate;
iterate=start;
temp= (struct node *)malloc(sizeof(struct node));
temp->data=insert;
temp->link=NULL;

if(start==NULL){
start=temp;
last=temp;
}
else{
while (iterate->link != NULL) {
iterate=iterate->link;
}
iterate->link=temp;
last=temp;
}
}

void checkpalindrom(struct node *tansverse){

if(tansverse == NULL){
return;
}

else {

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

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


}

int main()
{
addNode('A');
addNode('M');
addNode('I');
addNode('T');
addNode('T');
addNode('I');
addNode('M');
addNode('A');
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).
0 votes

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 by Salil Agrawal
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.
...