題目描述：
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up: Could you do it in O(n) time and O(1) space?
一刷題解（快慢指針）：
這題要我們檢查一個鏈表的值在順序輸出後的結果是否一個互文。我們可以通過快慢指針以及逆轉鏈表指向的思路來完成。首先我們創造兩個指針，一個指針的前移速度是另外一個個指針的兩倍，這樣一來，當快指針對達鏈表的終點時，慢指針就正處於鏈表的中間。
然後我們先將快指針還原到起點，再利用慢指針，一步一步將鏈表後半段的指向逆轉（從與前半段一樣指向後面逆轉為指向前半段），當慢指針到達鏈表的盡頭（舊鏈表的結尾，新鏈表的起點）後，形成一個「首末端指向中間」的鏈表結構，並擁有兩個分別位於鏈表兩端的指針，最後只要使這兩個指針均速前進即可。如果前進到各自的盡頭也沒有發現差異，代表這是一個「互文的鏈表」。
public class Solution {
public bool IsPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null)
{
fast = fast.next.next;
slow = slow.next;
}
fast = head;
slow = Reverse(slow); //反轉後半段的指向
//首端與末端同時向前移動
while(slow != null && fast != null)
{
if(fast.val != slow.val) { return false; }
fast = fast.next;
slow = slow.next;
}
return true;
}
ListNode Reverse(ListNode node)
{
ListNode prev = null;
ListNode curr = node;
while(curr != null)
{
ListNode originNext = curr.next;
curr.next = prev;
prev = curr;
curr = originNext;
}
return prev;
}
}