Checking if Linked List is palindromic

Question

Consider a linked list whose nodes are chars, so the list represents a string. How do you write a recursive routine to check whether the string is a palindrome such that the the said function starts unwinding the stack when it processes the character(s) at the middle of the string?

For example, suppose that my string is "madam". My recursive function looks something like:

bool isPalin(const node *startnode, const node *currentnode, const node *midpoint, ...);

When currentnode->data == 'd', the stack has to unwind.

I was asked this question for an interview; at the moment I can't think of any use for this question except as a very hard puzzle.

First thoughts: A very obvious (if inelegant) way is to:

1. Compute the midpoint of the list first.
2. If currentnode is "before" midpoint , push former into a stack manually. This can be decided by maintaining a counter.
3. Otherwise, unwind the manually maintained stack at every step of the recursion, and compare with the current character.

Any better ideas or fresh insights?

Answer 1

By "linked list", do you mean std::list?

template <typename BiDiIterator>
bool isPalindrome(BiDiIterator first, BiDiIterator last) {
    if (first == last) return true;
    --last;
    if (first == last) return true;
    if (*first != *last) return false;
    return isPalindrome(++first, last); // tail recursion FTW
}

isPalindrome(mylist.begin(), mylist.end());

I've used the fact that it's possible to iterate back from the end as well as forward from the start. It is not clear whether this is given by the question.

With a singly linked list you can run two iterators, one fast and one slow. On each call, increment the fast one twice and the slow one once. When the fast one reaches the end of the list, the slow one is at the midpoint (um, +/- 1 and taking account of odd-length and even-length lists). At that point, back out of your recursion comparing character values. Θ(n) complexity for runtime and memory use (not tail recursive).

I'd write the code, but it's time for bed here in the UK.

[Edit: morning all

template <typename FwdIterator>
std::pair<FwdIterator, bool> isPalindrome(FwdIterator slow, FwdIterator fast, FwdIterator last) {
    if (fast == last) return std::make_pair(slow, true);
    ++fast;
    if (fast == last) return std::make_pair(++slow, true);
    ++fast;
    FwdIterator next = slow;
    std::pair<FwdIterator, bool> result = isPalindrome(++next, fast, last);
    if (result.second == false) return result;
    if (*slow != *(result.first)) return std::make_pair(slow, false);
    ++(result.first);
    return result;
}

...

isPalindrome(mylist.begin(), mylist.begin(), mylist.end()).second;

If, for some bizarre reason, your linked list doesn't provide an iterator, then hopefully the equivalent code with if (fast->next == 0), fast = fast->next, etc, is obvious. And of course you can tidy up the user interface with a wrapper.

I think you can avoid the additional storage if you're allowed to temporarily modify the list, by reversing the list up to "slow" as you descend, then reversing it again as you ascend. That way you don't need to store a copy of slow across the recursive call: instead you can return an extra pointer for the caller to follow. I'm not going to bother, though.

]

Answer 2

Modulo thorny details this one's easy.

First, find the midpoint by calling recursively moving one pointer just one step but other two steps. When two-step pointer reaches end one-step pointer is at middle. Thorny thing: even versus odd length list.

Then back up (returning from the recursive calls), and while backing move midpointer one step forward for each return. Just compare that node's contents with contents available as routine argument during descent.

Cheers & hth.,