Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
思路：
這道題讓我們判斷鏈表是否為回文鏈表疚漆。鏈表不能根據(jù)坐標(biāo)來訪問，只能從頭開始遍歷。根據(jù)回文串的特點出牧，需要找到鏈表的中點筋现，需要用快慢指針來實現(xiàn)庭瑰。設(shè)置fast和slow兩個指針局装，每次慢指針走一步反症，快指針走兩步蚂斤〈孓啵快指針走到終點時，慢指針的位置就是中點的位置。每次慢指針走的時候?qū)⒅荡嫒霔Ｖ邪浦危冗_到中點時岗钩，鏈表的前半段都存入棧中了，由于棧的后進先出的性質(zhì)肖油，就可以和后半段鏈表按照回文串的對應(yīng)順序進行比較了兼吓。
var isPalindrome = function(head) {
if(!head || !head.next) return true;
var slow=head;
var fast=head;
var stack=[];
stack.push(head.val);
while(fast.next && fast.next.next){
slow=slow.next;
fast=fast.next.next;
stack.push(slow.val);
}
if(!fast.next) stack.pop();
while(slow.next){
slow=slow.next;
var tmp=stack.pop();
if(tmp !=slow.val) return false;
}
return true;
};
