給定一個(gè)鏈表的 頭節(jié)點(diǎn) head ，請(qǐng)判斷其是否為回文鏈表。

如果一個(gè)鏈表是回文，那么鏈表節(jié)點(diǎn)序列從前往后看和從后往前看是相同的。

示例 1：

輸入: head = [1,2,3,3,2,1]
輸出: true

示例 2：

輸入: head = [1,2]
輸出: false

提示：
鏈表 L 的長(zhǎng)度范圍為 [1, 105]
0 <= node.val <= 9

進(jìn)階：能否用 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/aMhZSa
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解題思路及方法

用線性表按序存儲(chǔ)每一個(gè)節(jié)點(diǎn)，然后用雙指針比較是常規(guī)的辦法，但是會(huì)用O(n)的空間。我們采用將鏈表后半部分反轉(zhuǎn)，然后將前半部分后半部分對(duì)比值即可在O(1)的空間解決。

我們用快慢指針找到前半部分最后一個(gè)節(jié)點(diǎn)，如果鏈表長(zhǎng)度為奇數(shù)則slow指向中間節(jié)點(diǎn)，為偶數(shù)指向前半部分節(jié)點(diǎn)的末尾節(jié)點(diǎn)。我們用mid = slow.next記錄后半部分開頭，然后反轉(zhuǎn)后半部分鏈表，并對(duì)比值即可。

/**
 * 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) return true;

        // 快慢指針找中點(diǎn)
        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 反轉(zhuǎn)后半部分鏈表
        ListNode mid = reverse(slow.next);
        ListNode pt1 = mid;
        ListNode pt2 = head;
        boolean res = true;
        while (res && pt1 != null) {
            if (pt1.val != pt2.val) res = false;
            pt1 = pt1.next;
            pt2 = pt2.next;
        }

        // 恢復(fù)鏈表
        slow.next = reverse(mid);
        
        return res;
    }

    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;

            // 移動(dòng)指針
            prev = curr;
            curr = next;
        }

        return prev;
    }
}

結(jié)果如下：