leetcode：234. 回文链表

题目

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

示例 1：

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

示例 2：

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

解答 & 代码

/**
 * 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 {
private:
    // 反转链表
    ListNode* reverseNode(ListNode* head)
    {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur != nullptr)
        {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
public:
    bool isPalindrome(ListNode* head) {
        // 1. 找到链表中点（快慢指针）
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 最终 slow 就是链表中点
        // 若链表长为奇数，则是中间节点；若链表长为偶数，则是第二个中间节点
        ListNode* mid = slow;
        // 若 fast == nullptr，则链表长为偶数，则 mid 就是右半部分链表的起点
        // 若 fast ！= nulptr，则链表长为奇数，则 mid->next 才是右半部分链表的起点
        ListNode* rightHead = fast == nullptr ? mid : mid->next;
        // 2. 将右半部分链表进行翻转
        rightHead = reverseNode(rightHead);
        // 3. 同时遍历左、右两半链表，如果都相同，则原链表是回文链表，否则不是
        ListNode* curL = head;
        ListNode* curR = rightHead;
        while(curR != nullptr)
        {
            if(curL->val != curR->val)
                return false;
            curL = curL->next;
            curR = curR->next;
        }
        return true;
    }
};

复杂度分析：设链表常委 N

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

执行结果：

执行结果：通过
执行用时：212 ms, 在所有 C++ 提交中击败了 25.31% 的用户
内存消耗：111.4 MB, 在所有 C++ 提交中击败了 73.00% 的用户