CareerCup

geeksforgeeks.org/archives/1072

count number of element in the list, O(n).
break list at n/2 and invert the second part of the list. O(n)
compare node by node to verify.
Once cone, invert the second list and link its head to the tail for first list.
Overall complexity O(n), space complexity const.

I will put all the elements in the LL in a String. After that I will check if that String is palindrome by either :
a) reversing the string and comparing
b) checking it myself for example:

public static boolean isPalindrome(char[] data, int start, int end) {
		int len = (end - start) + 1;
		for (int cursor = start; cursor < start + (len / 2); cursor++) {
			if (data[cursor] != data[end - cursor + start])
				return false;
		}
		return true;
	}

bool ispalin(node** head,node* last)
{
	if(last->next==NULL) return true;
	cout<<"!!! comparing "<<(*head)->ch<<" "<<last->ch<<" "<<last->next<<" "<<(*head)->next<<" "<<head<<" "<<last<<endl;
	bool temp = (ispalin(head,last->next) && ((*head)->ch == last->ch));
	cout<<"comparing "<<(*head)->ch<<" "<<last->ch<<" "<<last->next<<" "<<(*head)->next<<" "<<head<<" "<<last<<endl;
	(*head)=(*head)->next;
	return temp;
}
cout<<ispalin(&head,temp)<<endl;;

bool ispalin(node** head,node* last)
{
	if(last->next==NULL) return true;
	bool temp = (ispalin(head,last->next) && ((*head)->ch == last->ch));
	(*head)=(*head)->next;
	return temp;
}
cout<<ispalin(&head,temp)<<endl;

1)Take two pointers
2) Traverse the first pointer to the end of the LL
3) Now increment the second pointer by 1 and decrement the first pointer by 1.
4) Compare their values in the position.
5) If there is a mismatch before the pointers intercept then its not a palindrome.

so you require n+n/2 passes .. hence the complxity would be O(n)