讀完本文，你可以去力扣拿下如下題目：
-----------
我們之前有兩篇文章寫了回文串和回文序列相關(guān)的問題。
尋找回文串的核心思想是從中心向兩端擴(kuò)展：
string palindrome(string& s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.size()
&& s[l] == s[r]) {
// 向兩邊展開
l--; r++;
}
// 返回以 s[l] 和 s[r] 為中心的最長回文串
return s.substr(l + 1, r - l - 1);
}
因?yàn)榛匚拇L度可能為奇數(shù)也可能是偶數(shù)，長度為奇數(shù)時(shí)只存在一個(gè)中心點(diǎn)，而長度為偶數(shù)時(shí)存在兩個(gè)中心點(diǎn)，所以上面這個(gè)函數(shù)需要傳入l和r。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
而判斷一個(gè)字符串是不是回文串就簡(jiǎn)單很多，不需要考慮奇偶情況，只需要「雙指針技巧」，從兩端向中間逼近即可：
bool isPalindrome(string s) {
int left = 0, right = s.length - 1;
while (left < right) {
if (s[left] != s[right])
return false;
left++; right--;
}
return true;
}
以上代碼很好理解吧，因?yàn)榛匚拇菍?duì)稱的，所以正著讀和倒著讀應(yīng)該是一樣的，這一特點(diǎn)是解決回文串問題的關(guān)鍵。
下面擴(kuò)展這一最簡(jiǎn)單的情況，來解決：如何判斷一個(gè)「單鏈表」是不是回文。
一、判斷回文單鏈表
輸入一個(gè)單鏈表的頭結(jié)點(diǎn)，判斷這個(gè)鏈表中的數(shù)字是不是回文：
/**
* 單鏈表節(jié)點(diǎn)的定義：
* public class ListNode {
* int val;
* ListNode next;
* }
*/
boolean isPalindrome(ListNode head);
輸入: 1->2->null
輸出: false
輸入: 1->2->2->1->null
輸出: true
這道題的關(guān)鍵在于，單鏈表無法倒著遍歷，無法使用雙指針技巧。那么最簡(jiǎn)單的辦法就是，把原始鏈表反轉(zhuǎn)存入一條新的鏈表，然后比較這兩條鏈表是否相同。關(guān)于如何反轉(zhuǎn)鏈表，可以參見前文「遞歸操作鏈表」。
其實(shí)，借助二叉樹后序遍歷的思路，不需要顯式反轉(zhuǎn)原始鏈表也可以倒序遍歷鏈表，下面來具體聊聊。
對(duì)于二叉樹的幾種遍歷方式，我們?cè)偈煜げ贿^了：
void traverse(TreeNode root) {
// 前序遍歷代碼
traverse(root.left);
// 中序遍歷代碼
traverse(root.right);
// 后序遍歷代碼
}
在「學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的框架思維」中說過，鏈表兼具遞歸結(jié)構(gòu)，樹結(jié)構(gòu)不過是鏈表的衍生。那么，鏈表其實(shí)也可以有前序遍歷和后序遍歷：
void traverse(ListNode head) {
// 前序遍歷代碼
traverse(head.next);
// 后序遍歷代碼
}
這個(gè)框架有什么指導(dǎo)意義呢？如果我想正序打印鏈表中的val值，可以在前序遍歷位置寫代碼；反之，如果想倒序遍歷鏈表，就可以在后序遍歷位置操作：
/* 倒序打印單鏈表中的元素值 */
void traverse(ListNode head) {
if (head == null) return;
traverse(head.next);
// 后序遍歷代碼
print(head.val);
}
說到這了，其實(shí)可以稍作修改，模仿雙指針實(shí)現(xiàn)回文判斷的功能：
// 左側(cè)指針
ListNode left;
boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
boolean traverse(ListNode right) {
if (right == null) return true;
boolean res = traverse(right.next);
// 后序遍歷代碼
res = res && (right.val == left.val);
left = left.next;
return res;
}
這么做的核心邏輯是什么呢？實(shí)際上就是把鏈表節(jié)點(diǎn)放入一個(gè)棧，然后再拿出來，這時(shí)候元素順序就是反的，只不過我們利用的是遞歸函數(shù)的堆棧而已。
當(dāng)然，無論造一條反轉(zhuǎn)鏈表還是利用后續(xù)遍歷，算法的時(shí)間和空間復(fù)雜度都是 O(N)。下面我們想想，能不能不用額外的空間，解決這個(gè)問題呢？
二、優(yōu)化空間復(fù)雜度
更好的思路是這樣的：
1、先通過「雙指針技巧」中的快慢指針來找到鏈表的中點(diǎn)：
ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 指針現(xiàn)在指向鏈表中點(diǎn)
2、如果fast指針沒有指向null，說明鏈表長度為奇數(shù)，slow還要再前進(jìn)一步：
if (fast != null)
slow = slow.next;
3、從slow開始反轉(zhuǎn)后面的鏈表，現(xiàn)在就可以開始比較回文串了：
ListNode left = head;
ListNode right = reverse(slow);
while (right != null) {
if (left.val != right.val)
return false;
left = left.next;
right = right.next;
}
return true;
至此，把上面 3 段代碼合在一起就高效地解決這個(gè)問題了，其中reverse函數(shù)很容易實(shí)現(xiàn)：
ListNode reverse(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
算法總體的時(shí)間復(fù)雜度 O(N)，空間復(fù)雜度 O(1)，已經(jīng)是最優(yōu)的了。
我知道肯定有讀者會(huì)問：這種解法雖然高效，但破壞了輸入鏈表的原始結(jié)構(gòu)，能不能避免這個(gè)瑕疵呢？
其實(shí)這個(gè)問題很好解決，關(guān)鍵在于得到p, q這兩個(gè)指針位置：
這樣，只要在函數(shù) return 之前加一段代碼即可恢復(fù)原先鏈表順序：
p.next = reverse(q);
篇幅所限，我就不寫了，讀者可以自己嘗試一下。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
三、最后總結(jié)
首先，尋找回文串是從中間向兩端擴(kuò)展，判斷回文串是從兩端向中間收縮。對(duì)于單鏈表，無法直接倒序遍歷，可以造一條新的反轉(zhuǎn)鏈表，可以利用鏈表的后序遍歷，也可以用棧結(jié)構(gòu)倒序處理單鏈表。
具體到回文鏈表的判斷問題，由于回文的特殊性，可以不完全反轉(zhuǎn)鏈表，而是僅僅反轉(zhuǎn)部分鏈表，將空間復(fù)雜度降到 O(1)。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對(duì)應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標(biāo)星！
