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

I think we dont need an extra space for this. And this can be done with O(n) complexity.

Modifying Philip's solution:

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:

Have another pointer at the start of the linked-list (start pointre) and now - move the start pointer and the slow pointer one by one and compare them - if they are not equal, return false - if the slow pointer reaches the end of the list, it is a palindrome

This is O(n) time complexity and no extra space is required.

Answer 2

Just paste my implementation so we could compare with each others, full test here:

/**
 * Given a circular single linked list and the start pointer, check if it is a palindrome
 * use a slow/fast pointer + stack is an elegant way
 * tip: wheneve there is a circular linked list, think about using slow/fast pointer
 */

#include <iostream>
#include <stack>
using namespace std;

struct Node
{
    char c;
    Node* next;

    Node(char c) {this->c = c;}
    Node* chainNode(char c)
    {
        Node* p = new Node(c);
        p->next = NULL;
        this->next = p;
        return p;
    }
};

bool isPalindrome(Node* pStart)
{
    Node* pSlow = pStart;
    Node* pFast = pStart;

    stack<Node*> s;
    bool bEven = false;
    while(true)
    {
        // BUG1: check fast pointer first
        pFast = pFast->next;
        if(pFast == pStart)
        {
            bEven = false;
            break;
        }
        else
        {
            pFast = pFast->next;
            if(pFast == pStart)
            {
                bEven = true;
                break;
            }
        }

        pSlow = pSlow->next;
        s.push(pSlow);

    }
    if(s.empty()) return true; // BUG2: a, a->b->a
    if(bEven) pSlow = pSlow->next; // BUG3: a->b->c->b->a, a->b->c->d->c->b->a: jump over the center pointer

    while(!s.empty())
    {
        // pop stack and advance linked list
        Node* topNode = s.top();
        s.pop();
        pSlow = pSlow->next;

        // check
        if(topNode->c != pSlow->c)
        {
            return false;
        }
        else
        {
            if(s.empty()) return true;
        }
    }

    return false;
}

Answer 3

Since you know the Linked List does make a cycle, and you are only looking for palindromes starting at head, you can make this easier on yourself.

A -> B -> C -> B -> A

In this case, start with a pointer at head (call it H), and a pointer at head.Left() (call it T).

Now keep moving the head pointer H to the right, and the tail pointer T to the left.

As you walk the list, verify that the values of those elements are equal (i.e. a palindrome).

Your stopping condition however take a bit more. There are two cases:

• Both pointers end point at the same element (i.e. odd number of elements)
• The H pointer is pointing at the element just to the right of T.

So, you stop if H==T or if H==(T.Right()).

Using this approach (or similar) you visit each element just once.

Use the Tortoise and Hare approach as in the other solutions if you don't know if the linked list is cyclic.

Answer 4

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.

Answer 5

This is in pseudo-Haskell (I can't remember the exact syntax these days) and I've written for the non-circular case -- to fix that, just replace the clause matching against [] with whatever condition you use to identify you've come full circle.

p(xs) = q(xs, Just(xs)) != Nothing


q([], maybeYs) = maybeYs

q(x : xs, Nothing) = Nothing

q(x : xs, maybeYs) =
    let maybeZs = q(xs, maybeYs) in
    case maybeZs of
        Nothing        -> Nothing
        Just (x :: zs) -> Just(zs)
        otherwise      -> Nothing