AlgoPressAppearance
题目描述
https://leetcode.cn/problems/palindrome-linked-list
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1： 
输入：head = [1,2,2,1]
输出：true
示例 2： 
输入：head = [1,2]
输出：false
提示：
- 链表中节点数目在范围[1, 10^5] 内
- 0 <= Node.val <= 9
进阶：你能否用O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路
简单方法是把链表导入到数组中，然后首尾判断，过程略。
进阶：找到链表中点，然后反转后半部分链表，再进行比较
参考代码
csharp
public class Solution {
public bool IsPalindrome(ListNode head) {
//进阶，使用快慢指针，分别往后，找到链表的中点
//然后将后半部分反转，再和前半部分比较是否回文
//细节：注意奇偶数量判断
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next!= null){
slow = slow.next;
fast = fast.next.next;
}
//反转后半部分
ListNode pre = null;
//根据奇偶判断下半部分开始的节点
ListNode cur = fast == null ? slow : slow.next;
while(cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
slow = head;
fast = pre;
//比较 slow 和 fast，以fast结束为标志
while(fast != null){
if(slow.val != fast.val){
return false;
}
slow = slow.next;
fast = fast.next;
}
return true;
}
}