234. 迴文鏈表

思路

迴文指的是正著跟倒著看一模一樣的一串文字，比如racecar，以這題為例子，$[1,2,3,2,1]$ 就是一個迴文。
由於正著跟反著長一樣，只需要判斷一半的長度就行了。
第一個數字跟最後一個數字比較，第二個數字跟倒數第二個數字比較…以此類推。所以這個題目的做法是：

1. 先找到中點，斷開鏈表，走到底的同時將指針反轉，
2. 再讓指針從兩端出發，判斷是否相同。

程式碼

鏈表

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == nullptr || head -> next == nullptr) return true;
        
        ListNode *fast = head, *slow = head;
        while(fast -> next != nullptr && fast -> next -> next != nullptr) {
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        
        // 此時慢指針在中間(如果偶數，在左邊)，將右邊區域反轉
        ListNode *pre = nullptr, *cur = slow, *nxt;
        while(cur != nullptr) {
            nxt = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = nxt; 
        }
        
        ListNode *left = head, *right = pre;
        while(left != nullptr && right != nullptr) {
            if(left -> val != right -> val) {
                return false;
            }
            left = left -> next;
            right = right -> next;
        }
        return true;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$