Is Singly Linked List a Palindrome ??

Question

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

Answer 1

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

Comments

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).

Answer 2

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.

Comments

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.