如何檢查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; 
} 

注：我沒有測試過這一點，如果它的雙重鏈接它可能有錯誤或兩個，但一般的概念是有....

，那就更簡單了 - 遍歷一半然後在進行比較的兩個方向上進行迭代。