# 1.題目描述
判斷鏈表是否為回文結構。
根據這個題意，可以比較容易的使用一個棧來解決這個問題，那么此時的時間復雜度為`O(n)`，空間復雜度為`O(n)`，代碼如下：
~~~
/**
* 判斷鏈表是否是回文結構（方法一）
* 直接使用棧來，時間復雜度為O(n)，空間復雜度為O(n)
* 2022-1-8
*/
public boolean palindromicList_1(Node list){
if(list == null) return true;
Stack<Integer> stack = new Stack<>();
Node ptr = list;
// 數據壓入棧中
while(ptr != null){
stack.push(ptr.val);
ptr = ptr.next;
}
// 遍歷和彈棧同時進行
ptr = list;
while(ptr != null){
if(ptr.val != stack.pop()) return false;
ptr = ptr.next;
}
return true;
}
~~~
其思路也就是將鏈表中的所有數據裝入到棧中，然后再次遍歷這個鏈表，與彈出的棧元素進行比對。其實也就是將鏈表逆序后比對。
## 1.1 升級
那么能否做到使用時間復雜度為`O(n)`，空間復雜度為`O(1)`的算法來解決這個問題。
可以嘗試使用快慢指針來找鏈表的中點，然后分奇偶進行討論。可以做一個簡單的圖示：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截圖 2022-01-08 154905.png"/>
也就是說如果我們定義所需要找的中點為下一半鏈表元素的前一個節點位置，那么我們可以使用快慢指針統一處理，如果快指針的`next.next`等于空，那說明這個鏈表為偶數，且中點就位于此時的慢支針處。對應的我們可以寫出如下代碼邏輯：
~~~
Node fast = list, slow = list;
while(true){
if(fast.next != null){
fast = fast.next.next;
if(fast == null) break; // 偶數
if(fast.next == null) break; // 奇數
} else{
break;
}
slow = slow.next;
}
~~~
此時所需的中點的前一個節點也就是慢指針`slow`。
因為要求空間復雜度為`O(1)`，所以這里我們不能用棧的方式來解決這個問題。也就是我們這里可以嘗試將鏈表逆序，即逆序后半部分或者前半部分的鏈表，然后進行等值判斷即可。首先是鏈表的反轉：
~~~
/**
* 反轉鏈表
* @param list 鏈表
* @return 反轉后鏈表
*/
private Node reverseList(Node list) {
Node dummyNode = new Node(-1);
dummyNode.next = null;
Node ptr = list, temp = null;
while(ptr != null){
temp = ptr.next;
ptr.next = dummyNode.next;
dummyNode.next = ptr;
ptr = temp;
}
return dummyNode.next;
}
~~~
最終的代碼為：
~~~
/**
* 回文鏈表
* @param list 鏈表
* @return 是否為回文鏈表
*/
public boolean palindromicList_2(Node list) {
if (list == null) return true;
// 可以嘗試使用快慢指針來找鏈表的中點，然后分奇偶進行討論
Node fast = list, slow = list;
boolean isOdd = false;
while(true){
if(fast.next != null){
fast = fast.next.next;
if(fast == null) break; // 偶數
if(fast.next == null) { // 奇數
isOdd = true;
break;
}
} else{
break;
}
slow = slow.next;
}
if(isOdd) slow = slow.next;
Node midBefore = slow.next;
slow.next = null; // 斷鏈
Node reverseList = reverseList(midBefore);
// 等值判斷
Node temp = reverseList, qtr = list;
while(temp != null){
if(qtr.val != temp.val) return false;
temp = temp.next;
qtr = qtr.next;
}
// 把鏈表還原
slow.next = reverseList(reverseList);
return true;
}
~~~
