如何检查循环单链表是否是回文的？

Question

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

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

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

我想到了以下解决方案：

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

2. 从列表头开始。找到列表的长度和中间节点。现在反转这个列表的第二半部分。然后使用两个指针（一个指向起始位置，另一个指向中间加1的位置），检查值是否相同。如果不相同，则返回false。否则，继续直到我们再次到达起始节点。缺点：更改原始数据结构。

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

谢谢

- FunBoy

---

这个人为什么删除了他的答案，而那个答案中有一个类似于2的建议？ - AlanFoster

这是我的问题，您想要检查它是否包含一个回文从列表的“head”开始？还是回文可以从任何节点开始？ - st0le

@st0le 我在考虑回文从头开始的情况。这比回文可以从任何节点开始的情况更简单（或者我们需要在列表中找到最长回文的问题）。 - FunBoy

如果你可以使用额外的O(n)内存，那么你就不需要使用Floyd算法，也不需要在答案中展示任何聪明的技巧。只需将列表复制到一个数组中，并检查它是否是回文。完成。 - n. m.

Answer 1

由于您正在处理单向链表，所以您需要使用一些额外的空间或更多的时间。

您的第一种方法听起来很合理，但实际上您可以在一个运行中确定列表的长度和是否是回文序列。

我们修改所谓的弗洛伊德循环检测算法:

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

如果快指针到达列表的末尾，则慢指针指向列表的中间，现在:

• 慢指针前进到列表的末尾，并在每个步骤中：
• 它弹出堆栈中的一个元素并将其与当前列表元素进行比较（如果它们不相等，则返回false）
• 如果慢指针到达列表的末尾，则它是回文序列

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

- Philip

---

它很聪明，但仍需要O(n)的额外空间，并且是O(n^2)的复杂度（您需要将所有节点作为起点进行检查）- 这与将列表简单复制到数组中并进行检查类似。 - Baiyan Huang

@izprgmr 我认为给出了列表的头部，因此只有一个起始点和复杂度O(n)。 - Akashdeep Saluja

时间复杂度和空间复杂度均为O(n)。您只需遍历列表一次，且仅存储元素的一半。 - Philip

Philip：你的方法比我的好多了。谢谢 :) - FunBoy

Answer 2

我认为我们不需要额外的空间来完成这个任务。而且这可以用O(n)的复杂度来实现。

修改Philip的解决方案：

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

两个指针，“slow”和“fast”，都从列表头开始；慢指针每次迭代推进一个列表元素，快指针每次推进两个元素，在每一步中，慢指针将当前元素推入堆栈中，如果快指针到达列表的末尾，则慢指针指向列表的中间位置，现在：

在链表的起始点（起始点）处有另一个指针 - 现在移动起始指针和慢指针并逐个比较它们 - 如果它们不相等，则返回false - 如果慢指针到达列表的末尾，则它是回文

这是O(n)时间复杂度，不需要额外的空间。

- Rad

---

"慢指针将当前元素推入堆栈，这不会需要更多的空间吗？..." - AlanFoster

Answer 3

既然你知道链表可以形成循环，而且你只想从头开始查找回文，那么你可以让自己更容易些。

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

在这种情况下，从头部开始使用指针（称为H），以及从head.Left()开始的指针（称为T）。

现在继续将头指针H向右移动，将尾指针T向左移动。

在遍历列表时，验证那些元素的值是否相等（即回文）。

然而，您的停止条件需要更多的操作。有两种情况：

- 两个指针的结束点在同一个元素上（即元素数量为奇数） - H指针指向T右侧的元素。

因此，如果H==T或者H==(T.Right())，则停止。

使用这种方法（或类似方法），您只需访问每个元素一次。

如果不知道链接列表是否循环，请使用乌龟和兔子方法，如其他解决方案所示。

- Xantix

---

你的解决方案在列表是双向链表时很好。然而，在我的情况下，我没有这样的工具。它是一个只有指向节点单向指针的单向链表。 - FunBoy

Answer 4

这是伪Haskell代码（我现在记不清确切的语法了），我已经为非循环情况编写了代码 - 要解决这个问题，只需将匹配[]的子句替换为您用于识别已经完全循环的任何条件。

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

- Rafe

---

你能解释一下吗？我不熟悉 Haskell :( - Akashdeep Saluja

@AlanFoster - 你好。在这里，“高级”是一件好事，它意味着你可以用最少的低级别干扰（其中低级别是指机器或语言级别而不是问题级别）来表达自己。 - Rafe

@AkashdeepSaluja - 你好。这个程序从列表的末尾向前遍历，检查每个列表项是否与其相应的后面项匹配。Maybe类型有两个值：Nothing或Just(x)，其中x是某个值。在一个不太文明的语言中，你可能会使用null或non-null。函数q返回Nothing，如果此列表不是回文的话。 - Rafe

@AkashdeepSaluja - 了解我上面所做的事情的一种简单方法是将源列表与其颠倒版本进行比较。如果它们匹配，那就是一个回文。 - Rafe

@Rafe 我认为这是单向链表，无法从后往前遍历。 - Akashdeep Saluja

@AkashdeepSaluja - 当然可以。简单的方法是计算列表的反转并将其与原始列表进行比较。我所做的就是这样，只不过我使用调用堆栈来跟踪反转，而不是在内存中实际显现它。越想越觉得实际计算源列表的反转似乎是更好的选择。 - Rafe

Answer 5

把我的实现粘贴过来，这样我们就可以相互比较了，完整的test在这里：

/**
 * 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;
}

- Baiyan Huang