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

Question

我有一个关于C++中的单链表的问题。

如果array[0]=array[n]，array[1]=array[n-1]，…，则整数数组[0]称为对称数组。。。

例如：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;
}

注意：我还没有测试过，可能会有一两个错误，但总体思路是存在的。。。。

如果它是双重链接的，那就更容易了——中途迭代，然后双向迭代进行比较。

Answer 2

经典的方法是折叠列表并将元素推送到堆栈上，直到一半，然后从堆栈中弹出并与其余元素进行比较。

bool isPalindrome(forward_list<int> &l){
 forward_list<int> stack;
 auto it = l.begin();
 int len = 0;
 int i   = 0;
 while (it != l.end()){
   ++len;
   ++it;
 }
 if (len <= 1)
   return true;
 it = l.begin();
 while (i < (len / 2)) {
   stack.push_front(*it);
   ++i;
   ++it;
 }
 if ((len % 2) == 1) 
   ++it;
 while (!stack.empty()){
   if (stack.front() != *it)
     return false;
   stack.pop_front();
   ++it;
 }
 return true;
}
bool test_good(const int i){
 int j = i / 2;
 forward_list<int> l;
 for (int k = 0; k < j; k++){
   l.push_front(k); 
 }
 if (i % 2 == 1){
   l.push_front(j);
 }
 for (int k = j-1; k >= 0; k--){
   l.push_front(k);
 }
 return isPalindrome(l);
}
bool test_bad(const int i){
 forward_list<int> l;
 for (int k = 0; k < i; k++){
   l.push_front(k); 
 }
 l.push_front(i);
 l.push_front(i+1);
 return !isPalindrome(l);
}
int main(){
 for (int i = 0; i < 20; i++){
   cout << "test for " << i << "...";
   if (test_good(i))
     cout << "ok...";
   else return i;
   if (test_bad(i))
     cout << "ok." << endl;
   else return i;
 }
 return 0;
}

我使用了forward_list来实现堆栈，而不是使用专用的std::stack模板。此外，请注意，在使用T的泛型列表时，问题更为棘手，因为在堆栈上推送时不一定要实例化列表中值的副本，但不能推送对基元类型（如char或int）值的引用。对于这个问题，您必须提供两个不同的模板化实现，根据T的内容，它们将是enable_if。您可能还需要在模板中添加比较运算符。