234. Palindrome Linked List

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?

思路：

这道题让我们判断链表是否为回文链表。链表不能根据坐标来访问，只能从头开始遍历。根据回文串的特点，需要找到链表的中点，需要用快慢指针来实现。设置fast和slow两个指针，每次慢指针走一步，快指针走两步。快指针走到终点时，慢指针的位置就是中点的位置。每次慢指针走的时候将值存入栈中，等达到中点时，链表的前半段都存入栈中了，由于栈的后进先出的性质，就可以和后半段链表按照回文串的对应顺序进行比较了。

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