6

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

此类列表的示例可以是：a->b->c->b->a

现在我如何验证这个列表是否是一个pallindrome？

我想到了以下解决方案：

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

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

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

谢谢

4

5 回答 5

4

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

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

我们修改了所谓的弗洛伊德寻环算法：

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

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

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

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

于 2012-09-10T09:48:48.080 回答
0

我认为我们不需要额外的空间。这可以通过 O(n) 复杂度来完成。

修改菲利普的解决方案：

我们修改了所谓的弗洛伊德寻环算法：

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

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

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

于 2013-05-03T18:13:32.073 回答
0

这是伪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
于 2012-09-10T06:00:31.040 回答
0

由于您知道链表确实会形成一个循环，并且您只是在寻找从头开始的回文，因此您可以自己更轻松地完成此操作。

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

在这种情况下，从 head 处的指针（称为 H）和 head.Left() 处的指针开始（称为 T）。

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

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

但是，您的停止条件需要更多时间。有两种情况：

  • 两个指针都指向同一个元素（即奇数个元素）
  • H 指针指向 T 右侧的元素。

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

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

如果您不知道链表是​​否是循环的，请使用其他解决方案中的 Tortoise and Hare 方法。

于 2012-09-10T23:56:36.733 回答
0

只需粘贴我的实现，以便我们可以相互比较，在这里进行完整测试：

/**
 * 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;
}
于 2012-09-14T09:11:48.077 回答