回文鏈表
這個題屬實不算難，但是因為出在鏈表部分嫉嘀，很容易讓人誤會是使用鏈表的特性來解題猾浦，但是實際上還是使用普通的回文串判別的算法陆错。我第一次在想的時候想了半天怎么用單向鏈表的特性來解，結果發(fā)現(xiàn)是不行的金赦。
主要算法就是先遍歷一遍鏈表保存到其他能隨機訪問的數(shù)據(jù)結構中音瓷，然后再用兩個指針（廣義的）一個指頭一個指尾，向中間逼近的同時比較兩個指針指向內容的值夹抗。
下面就是兩個比較好的算法：
#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;
}
};
這個就是利用棧的特性比較鏈首元素和棧頂元素（最后入棧的元素即鏈尾元素）绳慎，然后鏈指針向后移，同時出棧一個元素，算法雖然挺好的但是實際速度不如用最普通的數(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;
}
};
這個就是之前提到的最簡單的不斷比較首元素和尾元素杏愤，相信都能很容易理解靡砌。
