之前在腾讯 WXG 微信支付一面的时候被问到这个题，要求必须用最优解法。

1、思路

• 该题的最优解是三个小题的结合：找链表中间节点、反转链表、判断两条链表是否相等；

• 时间复杂度 $O(N)$ ，空间复杂度 $O(1)$ 。

2、代码

class Solution {
public:
    ListNode* findMid(ListNode* head)           //找单链表中间节点
    {
        auto fast = head, slow = head;
        while (fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        return slow;
    }

    ListNode* reverseList(ListNode* head)       //反转后半部分链表
    {
        auto pre = head, cur = head->next;

        while (cur)
        {
            auto ne = cur->next;
            cur->next = pre;
            pre = cur, cur = ne;
        }

        head->next = nullptr;
        return pre;
    }

    bool isSame(ListNode* L1, ListNode* L2)     //判断链表的前后两部分是否相等
    {
        while (L2 != nullptr)       //这里只能用L2来判断，因为mid后面没有断尾
        {                           //若用L1来判断，则会从L1一直遍历到L2上面
            if (L1->val != L2->val)
            {
                return false;
            }

            L1 = L1->next, L2 = L2->next;
        }

        return true;
    }

    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return true;

        auto mid = findMid(head);
        auto L1 = head, L2 = mid->next;         //将链表从中一分为二

        L2 = reverseList(L2);
        return isSame(L1, L2);
    }
};