How to check if a circular single linked list is pallindrome or not?

Question

Question: I have a single linked list (i.e. a list with only pointer to the next node). Additionally this is a circular linked list (in this example, the last node has a pointer to the first node). Every node in the list contains a char.

An example of such a list can be: a->b->c->b->a

Now how can I verify if this list is a pallindrome?

I have thought of the following solution:

1. Start from the head of list. Find the length of the list and then the mid node. Now start again from the head of the list and keep pushing elements in stack until the mid. Now traverse the list from the mid and pop element. If the value of the popped element is equal to the value of the current node. if not, return false. otherwise, continue until the stack is empty and we've verified all chars. CONS: uses extra stack space :(

2. Start from the head of list. Find the length of the list and then the mid node. now reverse the 2nd half of this list. and then using 2 pointers (one pointing to start and the other pointing to the mid+1'th element), check if the values are same. if not, return false. else continue until we reach the start node again. CONS: Changing original data structure.

Is there a more elegant way to approach this problem (which hopefully does not use O(n) extra space or changes original list)? I'm interested in the algorithm rather than any specific implementation.

Thanks

Answer 1

Since you're dealing with a single linked list, you must use a little extra space or a lot more extra time.

Your first approach sounds reasonable, but you can determine the length of the list and palindrome-ness in a single run.

We modify the so-called Floyd's Cycle-Finding Algorithm:

• two pointers, "slow" and "fast", both start at the list head; the slow pointer advances one list element per iteration, the fast pointer two elements
• in each step, the slow pointer pushes the current element on the stack

if the fast pointer reaches the end of the list, the slow pointer points to the middle of the list, so now:

• the slow pointer advances to the end of the list, and in each step:
• it pops one element from the stack and compares it to the current list element (if they are not equal, return false)
• if the slow pointer reaches the end of the list, it is a palindrome

A little extra work is required for lists with an odd number of elements.