題目描述：

請判斷一個鏈表是否為回文鏈表。

示例 1:

輸入: 1->2輸出: false

示例 2:

輸入: 1->2->2->1輸出: true

思路分析：

迭代法：

避免使用 O(n)O(n) 額外空間的方法就是改變輸入。

我們可以將鏈表的前（后）半部分反轉（修改鏈表結構），然后將前半部分和后半部分進行比較。比較完成后我們應該將鏈表恢復原樣。雖然不需要恢復也能通過測試用例，但是使用該函數的人通常不希望鏈表結構被更改。

該方法雖然可以將空間復雜度降到 O(1)O(1)，但是在并發環境下，該方法也有缺點。在并發環境下，函數運行時需要鎖定其他線程或進程對鏈表的訪問，因為在函數執行過程中鏈表會被修改。

整個流程可以分為以下步驟：

找到前（后）半部分鏈表的尾節點。
反轉（前）后半部分鏈表。
判斷是否回文。

Python實現

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None:
            return True
        if head.next.next is None:
            return head.val == head.next.val
        fast = slow = q = head
        while fast.next and fast.next.next:#這里快指針的判讀條件跟判斷環形有一點不同
            fast = fast.next.next
            slow = slow.next
        def reverse_list(head):
            if head is None:
                return head
            cur = head
            pre = None
            nxt = cur.next
            while nxt:
                cur.next = pre
                pre = cur
                cur = nxt
                nxt = nxt.next
            cur.next = pre
            return cur
        p = reverse_list(slow.next)
        while p.next:
            if p.val != q.val:
                return False
            p = p.next
            q = q.next
        return p.val == q.val

java實現：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        ListNode slow=head;
        ListNode fast=head;
        ListNode pre=null,prepre=null;
       //反轉前半部分指針
        while(fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
            pre.next=prepre;
            prepre=pre;
        }
        if(fast != null) {
            slow = slow.next;
        }
       //比較前后部分指針是否相同
        while(pre!=null&&slow!=null){
            if(pre.val!=slow.val){
                return false;
            }
            pre=pre.next;
            slow=slow.next;
        }
        return true; 
    }
}

遞歸法：

currentNode 指針是先到尾節點，由于遞歸的特性再從后往前進行比較。frontPointer 是遞歸函數外的指針。若 currentNode.val != frontPointer.val 則返回 false。反之，frontPointer 向前移動并返回 true。

算法的正確性在于遞歸處理節點的順序是相反的，而我們在函數外又記錄了一個變量，因此從本質上，我們同時在正向和逆向迭代匹配。

所謂遞歸，即從上往下遞下去，然后再從下往上歸回來。

java實現代碼：

class Solution {
    private ListNode frontPointer;

    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }