這個題屬實不算難，但是因為出在鏈表部分，很容易讓人誤會是使用鏈表的特性來解題，但是實際上還是使用普通的回文串判別的算法。我第一次在想的時候想了半天怎么用單向鏈表的特性來解，結(jié)果發(fā)現(xiàn)是不行的。

主要算法就是先遍歷一遍鏈表保存到其他能隨機訪問的數(shù)據(jù)結(jié)構(gòu)中，然后再用兩個指針（廣義的）一個指頭一個指尾，向中間逼近的同時比較兩個指針指向內(nèi)容的值。

下面就是兩個比較好的算法：

#include<stack>
using namespace std;
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> s;
        ListNode* now=head;
        while(now!=NULL){
            s.push(now->val);
            now=now->next;
        }
        
        now=head;
        while(now!=NULL){
            if(s.top()!=now->val){
                return false;
            }
            s.pop();
            now=now->next;
        }
        return true;
    }
};

這個就是利用棧的特性比較鏈?zhǔn)自睾蜅ｍ斣兀ㄗ詈笕霔５脑丶存溛苍兀缓箧溨羔樝蚝笠?，同時出棧一個元素，算法雖然挺好的但是實際速度不如用最普通的數(shù)組...

class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        vector<int> vals;
        while(head)
        {
            vals.push_back(head->val);
            head = head->next;
        }
        for(int i = 0; i<vals.size()/2;++i )if(vals[i]!=vals[vals.size()-1-i])return 0;
        return 1;
    }
};

這個就是之前提到的最簡單的不斷比較首元素和尾元素，相信都能很容易理解。