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

Question

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

的整数数组[0..N]被称为对称如果数组[0] =阵列[n]的，阵列[1] =阵列[N-1]，...

例如：1 2 3 4 5 4 3 2 1

那么，有什么办法来检查一个整数单链表的对称性吗？

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

Answer 1

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

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。您可能还会将比较运算符添加到模板中。

Answer 2

如果“简单连接”你实际上意味着单独链接，那么你有复制它们的一半 - 是否使用递归的堆栈或数组。

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

注：我没有测试过这一点，如果它的双重链接它可能有错误或两个，但一般的概念是有....

，那就更简单了 - 遍历一半然后在进行比较的两个方向上进行迭代。