Palindromes in a Linked List

The other day I came across the following question:

Write a simple program for a Turing machine that can identify if a string of 0's and 1's on the tape is a palindrome or not.

I was discussing this with my friend who is an electronics engineer and who works with state machines a lot. Soon, our conversation turned into how would one solve the problem if the numbers were in a linked list.

I went home and thought about the problem.

There is the obvious O(n^2) solution:

1. Read the head
2. Go all the way to the tail
3. Compare.
4. Read the second item
5. Go all the way to tail - 1
6. Compare
7. And so on

Obviously, it is constant memory. But is there any way we could do it in O(n)?

Now, one fact that we didn't use is that the values in the linked list are 0's and 1's. Can this be used to our advantage?

I guess we can - if we encode the string into an integer.

So here is the revised algorithm:

1. Find the number of elements in the linked list - O(n)
   
2. Read half the number of elements and find the number (n) represented by the 1's and 0's
   
3. Read the remaining elements and pop the digits from n and compare the values

Now what if the linked list could have any kind of values?