c++ - 检查链表是否回文

Question

考虑一个节点为字符的链表，因此该列表表示一个字符串。你如何编写一个递归例程来检查字符串是否是回文上述函数在处理字符串中间的字符时开始展开堆栈？

例如，假设我的字符串是“madam”。我的递归函数类似于:

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

当 currentnode->data == 'd' 时，堆栈必须展开。

我在面试时被问到这个问题；目前我想不出这个问题有什么用，除非它是一个非常难的谜题。

第一个想法:一个非常明显(如果不够优雅)的方法是:

1. 首先计算列表的中点。
2. 如果 currentnode 是“before” 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) 运行时和内存使用的复杂性(非尾递归)。

我会写代码，但在英国该 sleep 了。

[编辑:早上好

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 的拷贝:相反，您可以返回一个额外的指针供调用者遵循。不过，我不会打扰。

]