題目網址：https://leetcode.cn/problems/palindrome-linked-list/

題意：判斷 linked list 是否迴文。

Solution：

想法：利用 876. Middle of the Linked List 的方法取得 linked list 的中點
然後 reverse 以 slow 為 head 的 linked list, 最後比較兩個 linked list 是否相等
(reverse linked list 可參考 206. Reverse Linked List)

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *slow = head, *fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // fast != NULL 代表 linked list 之 node 個數為奇數
        if (fast) {
            slow = slow->next; // 若為奇數, 則中點往後一位
        }

        slow = reverse(slow);

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

        return true;
    }

private:
    ListNode* reverse(ListNode* head){
        ListNode *prev = nullptr, *next = NULL;
        while (head) {
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
};
  • time：$O(n)$ ➔ 遍歷 linked list 中 $\dfrac{n}{2}$ 個元素
  • space：$O(1)$ ➔ 只需要常數空間