c++ - 如何在 C++ 中检查整数单链表的对称性？

Question

我对 C++ 中的单链表有疑问。

如果数组[0] = 数组[n], 数组[1] = 数组[n-1], ... 则整数数组[0..n] 称为对称数组

例如:1 2 3 4 5 4 3 2 1

那么，有什么方法可以检查整数单向链表的对称性吗？

我想过将它们的值复制到一个数组中，然后检查这个数组的对称性，但我认为这不好，因为链接列表的特征会丢失。

Answer 1

如果您所说的“简单链接”实际上是指单独链接，那么您必须复制其中的一半——无论是使用递归在堆栈上还是复制到数组。

bool is_symmetric(Node* p, int n)
{
    Value values[n / 2]; // use alloca or std::vector if your compiler doesn't support
    for (int i = 0; i < n / 2; ++i, p = p->next)
         values[i] = p->value;
    if ((n + 1) % 2) p = p->next; // for odd number of elements, middle one's ok
    for (; i >= 0; --i, p = p->next)
         if (values[i] != p->value)
             return false;
    return true;
}

注意:我还没有测试过这个，它可能会有一两个错误，但总体思路就在那里......

如果是双向链接，则更容易 - 迭代一半，然后在两个方向上迭代进行比较。