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

示例 1：

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

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

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
 

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

朴素做法

维护一个头插法的逆序链表reverseHead
遍历一遍链表 然后再用reverseHead和head进行比较是否相同

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* p = head;
        ListNode* reverseHead = nullptr;
        while(p){
            ListNode* tmp = new ListNode(p->val);
            tmp->next = reverseHead;
            reverseHead = tmp;
            p = p->next;
        }
        ListNode *a = head, *b = reverseHead;
        while(a && b){
            if(a->val != b->val){
                return false;
            }
            a = a->next;
            b = b->next;
        }
        return !(a || b);
    }
};

时间复杂度: O(n)
空间复杂度: O(n)

快慢指针法

利用快慢指针找到链表的中间结点 然后把后半部分链表原地逆置 然后再与前半部分进行比较
只需要判断与前半部分均相同即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode *p = slow->next; // 中间链表的下一个 解决奇数的情况 1 2 1 会变为1 回文判断只会判断前面的1
        ListNode* reverseHead = nullptr;
        while(p){
            ListNode *tmp = p->next;
            p->next = reverseHead;
            reverseHead = p;
            p = tmp;
        }
        slow->next = nullptr;

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

    }
};