# 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;
}
~~~
