检查链接列表是否是回文

Question

考虑一个链接列表,其节点是字符,因此列表代表一个字符串.你如何编写一个递归例程来检查字符串是否是回文,以便所述函数在处理字符串中间的字符时开始展开堆栈？

例如,假设我的字符串是"女士".我的递归函数看起来像:

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

什么时候currentnode->data == 'd',堆栈必须放松.

我被问到这个问题的面试; 目前我不能想到这个问题有什么用处,除非是一个非常难的谜题.

初步想法:非常明显(如果不优雅)的方式是:

1. 首先计算列表的中点.
2. 如果 currentnode 是"之前" midpoint ,则将前者手动推入堆栈.这可以通过维持计数器来决定.
3. 否则,在递归的每个步骤中展开手动维护的堆栈,并与当前字符进行比较.

有更好的想法或新的见解吗？

Answer 1

通过"链表",你的意思是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());

我已经使用了这样一个事实:它可以从头开始迭代,也可以从头开始.目前尚不清楚这是否由问题给出.

使用单链接列表,您可以运行两个迭代器,一个快速,一个慢.在每次通话时,将快速两次递增,将慢一次递增一次.当快速的一个到达列表的末尾时,慢速的一个到达中点(嗯,+/ - 1并考虑奇数长度和偶数长度列表).此时,退出比较字符值的递归.Θ(n)运行时和内存使用的复杂性(不是尾递归).

我会写代码,但现在是时候在英国睡觉了.

[编辑:早上好

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 (fast->next == 0),fast = fast->next等等,是显而易见的.当然,您可以使用包装器整理用户界面.

如果你被允许临时修改列表,你可以避免额外的存储,通过在下降时将列表反转为"慢",然后在你提升时再次反转它.这样您就不需要存储slow递归调用的副本:相反,您可以返回一个额外的指针供调用者遵循.不过,我不打算打扰.

]