给你一个单链表的头节点 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) 空间复杂度解决此题？

首先可以想到用快慢指针找到链表中间节点

对于奇数个节点为中间，对于偶数个节点为后半部分的起始节点

想要一边遍历一边比较，我们可以反转后半部分链表，这样就可以从尾开始遍历了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool isPalindrome(ListNode *head) {
        ListNode *h = head;
        ListNode *mid = head;
        while (h != nullptr && h->next != nullptr) {
            h = h->next->next;
            mid = mid->next;
        }

        // 反转后半部分
        ListNode *pre = nullptr;
        while (mid != nullptr) {
            ListNode *mm = mid->next;
            mid->next = pre;
            pre = mid;
            mid = mm;
        }

        h = head;
        while (pre != nullptr) {
            if (pre->val != h->val) {
                return false;
            }
            pre = pre->next;
            h = h->next;
        }
        return true;
    }
};