1：利用快慢指针先找到链表的中间节点(奇数为中间，偶数为中间两个中的第一个)，然后将后半部分链表进行翻转即可进行回文的比较。(或者翻转前半部分链表也是一样的).

这里是翻转前半部分链表。需要的注意：在翻转的过程中引用 head -> next 时，该值有可能被改变，即 line 28、29！

2：利用 hash，lefhash = lefhash * base + arr[i]，righash = (base^i) * arr[i] + righash.  (！这里的 base^i 表示 base 的 i 次方)

 1 class Solution {
 2 public:
 3     bool isPalindrome(ListNode* head) {
 4         if(head == nullptr || head -> next == nullptr) return true; // 只有 0 或 1 个节点
 5         auto ret = solve(head);
 6         while(ret.first && ret.second) {
 7             if(ret.first -> val != ret.second -> val) return false;
 8             ret.first = ret.first -> next;
 9             ret.second = ret.second -> next;
10         }
11         return true;
12     }
13 
14     // 利用快慢指针, 翻转中间处的链表, 即分成两部分, 并返回
15     pair<ListNode *, ListNode *> solve(ListNode *head) {
16         int len = 0;
17         ListNode *quick = head, *copyHead = head;
18         // 若链表节点为偶数, head 的位置为第一个; 若链表节点为奇数, head 的位置为中间
19         while(quick && quick -> next && quick -> next -> next) {
20             len += 2;
21             head = head -> next;
22             quick = quick -> next -> next;
23         }
24         if(quick) ++ len;
25         if(quick && quick -> next) ++ len;
26         // 翻转前半部分
27         ListNode *pre = nullptr;
28         auto nxt = head -> next;
29         while(copyHead != nxt) {
30             auto temp = copyHead -> next;
31             copyHead -> next = pre;
32             pre = copyHead;
33             copyHead = temp;
34         }
35         return {len % 2 ? pre -> next : pre, copyHead};
36     }
37 };