题目描述：

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

逻辑：

首先找到链表的中间节点，再使用双指针逐渐往两边遍历，如果遍历结束后发现两指针指向的值没有不相等，则返回true，否则返回false。

需要解决的问题有两个，不像数组无法用sizeof关键字直接求得链表的长度，也链表的数据结构不是连续内存，也就无法如数组一样双向遍历（i++或i--）。

第一个问题相应的方法有快慢指针，快慢指针都从链表头节点往后遍历，满指针一次向后走一步，快指针一次向后走两步。

若链表的节点个数为奇数，比方说n=2*k+1，在最后一个节点最后因为还有NULL的存在，所以从头节点至NULL节点一共为n=2*k+1步，所以快指针走k步后就正好指向最后一个节点，那么满指针则指向第k+1个节点，其实也就是最终间的节点。（n=k+1+k）

若节点个数为偶数，n=2*k，当快指针指向NULL时，一共走了k步，此时满指针指向第k+1个节点，也就是中间的右边的节点。（n=k+1+（k-1））

第二个问题相应的解决方法有链表逆转和栈，当找到中间节点后，如果是链表逆转，则将右边的链表进行逆转，然后比对两条链表的节点值是否完全一致。如果使用栈，则将中间节点左侧的所有节点入栈后，再逐个进行出栈，同时将出栈的节点值和从中间节点继续向右侧遍历的节点值进行比对。

#if 1
class Solution {// 876. 链表的中间结点ListNode* middleNode(ListNode* head) {ListNode* slow = head, *fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;}// 206. 反转链表ListNode* reverseList(ListNode* head) {ListNode* pre = nullptr, *cur = head;while (cur) {ListNode* nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}return pre;}public:bool isPalindrome(ListNode* head) {ListNode* mid = middleNode(head);ListNode* head2 = reverseList(mid);while (head2) {if (head->val != head2->val) { // 不是回文链表return false;}head = head->next;head2 = head2->next;}return true;}
};
#endif
#if 0
class Solution {
public:bool isPalindrome(ListNode* head) {stack<int>sk;ListNode* node = head;while (node) //遍历一遍并入栈{sk.push(node->val);node=node->next;}node=head;while(head&&head->val==sk.top()){head=head->next;sk.top();}if (sk.size() > 0) { return false; } //栈不为空则返回false，反之返回truereturn true;}
};
#endif