简单题的最优解不简单，之前腾讯WXG实习一面被问到过这个题，要求最优解我没想出来，思路如下：

1. 用双指针遍历找到链表中间节点；
2. 反转后半部分链表；
3. 从头遍历两条链表并比对。

此方法为最优解法，时间复杂度为$O(N)$，空间复杂度为$O(1)$。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) return true;

        ListNode *mid = findMid(head);              //找中点
        ListNode *l1 = head, *l2 = mid->next;       

        //上一题重排链表中这里使用mid->next = nullptr来切断链表，本题可以不用切断

        l2 = reverseList(l2);                       //反转链表

        return isSame(l1, l2);                      //判断两链表是否相同
    }

    ListNode* findMid(ListNode* head)               //下面三个方法都可以当模板来记
    {
        ListNode *fast = head, *slow = head;
        while (fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    ListNode* reverseList(ListNode* head)
    {
        if (head == nullptr) return nullptr;
        ListNode *pre = head, *cur = head->next;
        while (cur)
        {
            ListNode *ne = cur->next;
            cur->next = pre;
            pre = cur, cur = ne;
        }

        head->next = nullptr;
        return pre;
    }

    bool isSame(ListNode* l1, ListNode* l2)
    {
        ListNode *p1 = l1, *p2 = l2;
        while (p2)  //这里只能用p2，因为前面我们没有切断链表，若用p1则会一直走到后半段链表上
        {
            if (p1->val != p2->val) return false;
            p1 = p1->next, p2 = p2->next;
        }

        return true;
    }
};