今天的題單：

• Single Number

• Palindrome Linked List

136. Single Number

給定的 vector 中除了一個數字只出現一次外，其他的數字都出現兩次，我們要找出那個只出現一次的數字。在沒有限制條件的情況下，直覺想到的是用 hash map 紀錄出現過的數字次數。

但是題目要求要在 constant extra space 限制下解題，所以不能開 O(n) space

For any problem, the term “constant extra space” means that the space(memory) you have taken to solve the problem doesn't depend on the input variable.

思路：利用 XOR operation 性質

從下面的真值表可以觀察到 a XOR b 會在 a 和 b 不同的時候為 true，a 和 b 相同的時候為 false。

在電腦裡的整數都是以二進位的形式存的，當兩個數字 a 和 b 是相同時，a XOR b 結果會是 0，而 a XOR 0 結果會是 a。因此可以利用這個性質，把 vector 裡所有的數字都 XOR 起來，出現兩次的數字會抵消為 0，最後的結果就是只有出現一次的那個數字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            ans = ans ^ nums[i];
        }
        return ans;
    }
};

234. Palindrome Linked List

判斷給定的 linked list 是不是回文。題目要求需要 O(n) time 和 O(1) space。

思路：兩步驟，先找到 linked list 的中點，然後比較前後兩段 list。

• 找中點利用 two pointer (slow/fast)，O(n) time 和 O(1) space

• 要判斷回文，前半段要順著看，後半段要反著看。由於給定的 linked list 是單向的，後半段採用 recursive 的方式製造反向走訪。

  • 把 head 位置傳進去 recursive function，當後半的反向走訪開始後，每次跟當前 node 比較完就正向移動到下一個 node

/**
 * 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 {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        int length = 0;
        bool flag = true;
        
        // find the middle point
        while (fast != nullptr) {
            if (fast->next == nullptr)
                break;
            fast = fast->next->next;
            slow = slow->next;
            length += 2;
        }
        length--;

        if (length % 2 == 0) slow = slow->next;

        recursive(slow, &head, flag);

        return flag;
    }

    void recursive(ListNode* node, ListNode** forth, bool& flag) {
        if (node == nullptr) {
            return;
        }
        recursive(node->next, forth, flag);

        if (node->val != (*forth)->val) {
            flag = false;
        } else {
            *forth = (*forth)->next;
        }
    }
};

在討論區看到類似的解法，不過是把後半 list 轉向 (reverse list)。雖然一樣能達成判斷回文的目的，但是會破壞 linked list 結構。純解題沒有問題，但以設計角度來說，判斷回文的過程應該不預期會改變資料結構，所以我覺得 reverse list 做法不太恰當。