一、題目

??編寫(xiě)一個(gè)函數(shù)，檢查輸入的鏈表是否是回文的。

??點(diǎn)擊此處跳轉(zhuǎn)題目。

示例 1：

輸入： 1->2
輸出： false

示例 2：

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

進(jìn)階：

• 你能否用 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？

二、C# 題解

??使用 $O(n)$ 空間很容易寫(xiě)出來(lái)，只需要開(kāi)辟一個(gè)數(shù)組或者反向鏈表即可。這里為了實(shí)現(xiàn)進(jìn)階要求，在原鏈表上修改。首先將鏈表的前半部分翻轉(zhuǎn)，然后比較前后兩個(gè)鏈表是否相同，最后恢復(fù)原鏈表即可，具體實(shí)現(xiàn)細(xì)節(jié)見(jiàn)代碼注釋：

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/
public class Solution {public bool IsPalindrome(ListNode head) {int n = 0, i;ListNode p = head, q;bool result;// 統(tǒng)計(jì)鏈表長(zhǎng)度while (p != null) {p = p.next;n++;}if (n <= 1) return true;    // 長(zhǎng)度 <= 1，一定是回文串i = n / 2;                  // 長(zhǎng)度的一半，向下取整p = head;while (--i > 0) p = p.next; // 定位到鏈表中間q = p.next;p.next = null;              // 斷開(kāi)鏈表Reverse(head);              // 翻轉(zhuǎn)前半部分// 判斷鏈表前后兩部分是否相同if (n % 2 == 0) result = Same(p, q);else result = Same(p, q.next); // 奇數(shù)長(zhǎng)度的鏈表需要跳過(guò)最中間的元素// 恢復(fù)鏈表原狀Reverse(p);p.next = q;return result;}// 翻轉(zhuǎn)鏈表public ListNode Reverse(ListNode head) {ListNode p = null, q = head, r;while (q != null) {r = q.next;q.next = p;p = q;q = r;}return p;}// 比較兩個(gè)鏈表是否相同public bool Same(ListNode h1, ListNode h2) {while (h1 != null && h2 != null) {if (h1.val != h2.val) return false;h1 = h1.next;h2 = h2.next;}return h1 == null && h2 == null;}
}

• 時(shí)間復(fù)雜度：$O(n)$。
• 空間復(fù)雜度：$O(1)$。

??看了一下官方解法，發(fā)現(xiàn)還可以進(jìn)行優(yōu)化。使用快慢指針定位到中間節(jié)點(diǎn)，代碼會(huì)更加高級(jí)和優(yōu)雅hh。但是效率和上面統(tǒng)計(jì)長(zhǎng)度然后遍歷一半進(jìn)行定位的方式差不多，因?yàn)槎际潜闅v了一個(gè)半鏈表（快指針遍歷整個(gè)鏈表，慢指針遍歷半個(gè)鏈表），但是快慢指針這種方法它顯得高級(jí)呀哈哈！

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/
public class Solution {public bool IsPalindrome(ListNode head) {if (head == null || head.next == null) return true;ListNode p = head, q = p.next; // p：慢指針，q：快指針bool result;while (q != null && q.next != null) {q = q.next.next;           // q 前進(jìn)兩格if (q != null) p = p.next; // q 不為空，p 才前進(jìn)}ListNode r = p.next;           // 定位到后半段鏈表的首部p.next = null;                 // 斷開(kāi)鏈表Reverse(head);                 // 翻轉(zhuǎn)前半部分// 判斷鏈表前后兩部分是否相同if (q != null) result = Same(p, r);else result = Same(p, r.next); // 奇數(shù)長(zhǎng)度的鏈表需要跳過(guò)最中間的元素// 恢復(fù)鏈表原狀Reverse(p);p.next = r;return result;}// 翻轉(zhuǎn)鏈表public ListNode Reverse(ListNode head) {ListNode p = null, q = head, r;while (q != null) {r = q.next;q.next = p;p = q;q = r;}return p;}// 比較兩個(gè)鏈表是否相同public bool Same(ListNode h1, ListNode h2) {while (h1 != null && h2 != null) {if (h1.val != h2.val) return false;h1 = h1.next;h2 = h2.next;}return h1 == null && h2 == null;}
}

• 時(shí)間復(fù)雜度：$O(n)$。
• 空間復(fù)雜度：$O(1)$。

??修改過(guò)后，發(fā)現(xiàn)快慢指針跑出來(lái)的速度不如直接統(tǒng)計(jì)鏈表長(zhǎng)度來(lái)得快。果然，高端的代碼往往以最樸素的方法寫(xiě)出來(lái)~