algorithm - 如何检查循环单链表是否为回文？

Question

问题:我有一个单链表(即只有指向下一个节点的指针的列表)。此外，这是一个循环链表(在这个例子中，最后一个节点有一个指向第一个节点的指针)。列表中的每个节点都包含一个字符。

这样一个列表的例子可以是:a->b->c->b->a

现在我如何验证这个列表是否是回文串？

我想到了以下解决方案:

1. 从列表的头部开始。找到列表的长度，然后找到中间节点。现在再次从列表的头部开始，并继续将元素插入堆栈直到中间。现在从 mid 和 pop 元素遍历列表。如果出栈元素的值等于当前节点的值。如果不是，则返回 false。否则，继续直到堆栈为空并且我们已经验证了所有字符。缺点:使用额外的堆栈空间:(

2. 从列表的头部开始。找到列表的长度，然后找到中间节点。现在反转此列表的第二部分。然后使用 2 个指针(一个指向开始，另一个指向 mid+1'th 元素)，检查值是否相同。如果不是，则返回 false。否则继续，直到我们再次到达起始节点。缺点:更改原始数据结构。

有没有更优雅的方法来解决这个问题(希望不使用 O(n) 额外空间或更改原始列表)？我感兴趣的是算法而不是任何特定的实现。

谢谢

Answer 1

由于您处理的是单个链表，您必须使用一点额外的空间或更多的额外时间。

您的第一种方法听起来很合理，但您可以在单次运行中确定列表的长度和回文数。

我们修改了所谓的 Floyd 循环查找算法:

• 两个指针，“slow”和“fast”，都从链表头开始；慢指针每次迭代前进一个列表元素，快指针每次迭代两个元素
• 在每一步中，慢指针将当前元素压入栈中

如果快指针到达链表末尾，慢指针指向链表中间，所以现在:

• 慢指针前进到列表的末尾，并且在每一步中:
• 它从堆栈中弹出一个元素并将其与当前列表元素进行比较(如果它们不相等，则返回false)
• 如果慢指针到达链表末尾，则为回文

对于元素数量为奇数的列表，需要做一些额外的工作。