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.nextwhile (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.nextwhile (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。
)
