Given a singly linked list, determine if it is a palindrome.

一开始想用栈，但是试来试去发现写不出来遂放弃，后来想想再不济可以转换成数组然后分别两头扫，但是这样就用了O(n) 的空间，再进一步，可不可以在链表里模拟呢。思前想后发现是可以的，只要把链表的头尾接到一起形成个环，然后头指针每次一动1步，尾指针每次移动 len - 1 步就行了，len 是链表的长度。

这样我实现了算法1：

/** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} head * @return {boolean} */var isPalindrome = function(head) {    if (!head) return true;    var tail = head;    var len = 0;    while (tail && tail.next) {        len++;        tail = tail.next;    }    len++;    tail.next = head;        var ring = len;    while (tail.val == head.val) {        if (tail === head || ring === 0) return true;        head = head.next;        ring--;        for (var i = 0; i < len - 1; i++) {            tail = tail.next;        }    }    return false;};

这个算法是正确的，但是很遗憾TLE 了。头尾相接的做法其实是用取模运算的原理来模拟指针运动，可以运用相同原理适当改写程序而避免头尾相接，算法2：

/** * @param {ListNode} head * @return {boolean} */var isPalindrome = function(head) {    if (!head) return true;    var tail = head;    var len = 0;    while (tail && tail.next) {        len++;        tail = tail.next;    }    len++;        var p1 = head;    var p2 = head;    var k = 1;        for (var i = 0; i < len - k; i++) {        p2 = p2.next;    }        while (p1 && p2 && p1.val == p2.val) {        if (p1 === p2 || k == len) return true;        k++;        p2 = head;        for (var i = 0; i < len - k; i++) {            p2 = p2.next;        }                p1 = p1.next;    }        return false;};

算法1，2 的区别就是有卵用和没卵用的区别，但是貌似头尾相接要更简洁一点，但是同样是TLE。

后面看了些提示又想出一个土办法：可以copy 一个链表出来然后反转，然后两个链表一起遍历对比，算法3:

/** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} head * @return {boolean} */var reverseList = function(head) {    if (!head) return null;    var prev = null;    var now = head;    var next = head.next        while (now) {        now.next = prev;        prev = now;        now = next;        if (next) next = next.next;    }    return prev;};var copyList = function(head) {    var p = new ListNode(-1);    var c = p;    while (head) {        var n = new ListNode(head.val);        c.next = n;        c = n;        head = head.next;    }    return p.next;}var isPalindrome = function(head) {    if (!head) return true;    var copy = copyList(head);    var rev = reverseList(copy);    var p = rev;    var q = head;    while (p && q) {        if (p.val !== q.val) return false;        p = p.next;        q = q.next;    }    return true;};

这个是可以accept 的，但是是用了O(n) 额外空间，那么转换成数组或者字符串两头扫八成也是可以通过的。

最后看了一些答案，发现虽然翻转整个链表需要O(n)的额外空间，但是翻转一半的话就不需要，那么只需要把原链表翻转一半，然后两头扫就行，关键是怎么找到一半。

要么先扫一遍得到长度，再扫一遍取一半。但是有更简洁的办法可以一次遍历就找出中点，就是快慢指针。设想一个指针按正常速度遍历链表，另一个指针的速度是他的一半，那么当正常速度指针遍历结束的时候，半速指针刚好在链表的中间，利用这个技巧找到链表中点，然后从中点开始翻转，然后两头扫就可以。算法4:

/** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} head * @return {boolean} */var reverseList = function(head) {    if (!head) return null;    var prev = null;    var now = head;    var next = head.next        while (now) {        now.next = prev;        prev = now;        now = next;        if (next) next = next.next;    }    return prev;};var isPalindrome = function(head) {    if (!head) return true;    var fast = head;    var slow = head;    var m = 1;    while (fast) {        if (m === 0) {            slow = slow.next;        }        m = (m + 1) % 2;        fast = fast.next;    }        var tail = reverseList(slow);    while (head && tail) {        if (head.val !== tail.val) return false;        head = head.next;        tail = tail.next;    }    return true;    };

利用一个整数变量m 来控制slow 指针的速度，fast 每走两步，slow走一步。然后reverse 另一半，两头扫。整个过程还是很简洁的，Accepted。