思路：

题目的主要信息：

• 链表至少为1，不用担心为空
• 判断单链表中的数值是否是回文

因为比较回文的基本思路是最前和最后比较，然后依次向中间靠齐，但是这是一个单链表，无法向前，所以我们要用另外的方法使它逆序。

方法一：中点逆链表法

具体做法：

找到链表长度，然后找到链表中间结点，从中间结点开始往后将链表指针反过来。然后比较前半部分和后半部分即可，因为后半部分相当于是逆序。

class Solution {
public:
    ListNode* reverse(ListNode* head) { //反转链表指针
        ListNode* prev = NULL;
        while (head != NULL) {
            ListNode* next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
    return prev;
}
    bool isPail(ListNode* head) {
        ListNode* p = head;
        int n = 0;
        while(p != NULL){ //找到链表长度
            n++;
            p = p->next; 
        }
        n = n / 2; //中点
        p = head;
        while(n > 0){
            p = p->next;
            n--;
        }
        p = reverse(p);  //中点处反转
        ListNode* q = head;
        while (p != NULL) {
            if (p->val != q->val) //比较判断节点值是否相等
                return false;
            p = p->next;
            q = q->next;
        }
        return true;
    }
};

复杂度分析：

• 时间复杂度：O(n)，找到链表长度、找到中点，两部分比较都是O(n)
• 空间复杂度：O(1)，没有额外空间

方法二：栈逆序法

具体做法：

因为需要逆序比较，因此可以首先遍历一次链表，并用栈来保存每个数值。 第二次遍历即可依次与出栈的数值比较，因为栈是先进后出，本身就是一个逆序。

class Solution {
public:
    bool isPail(ListNode* head) {
        ListNode* p = head;
        stack<int> s;
        while(p != NULL){
            s.push(p->val);
            p = p->next;
        }
        p = head;
        while(!s.empty()){
            if(p->val != s.top())
                return false;
            s.pop();
            p = p->next;
        }
        return true;
    }
};

复杂度分析：

• 时间复杂度：O(n)，两次遍历都是O(n)
• 空间复杂度：O(n)，使用了额外的栈空间