# 234 - Palindrome Linked List

解法一 - Fast & Slow Pointer

這題的解法還滿巧妙的，步驟如下：

1. 先用 fast & slow pointer 找到 list 的中點

2. reverse 後半 list

3. 分別走前半 list 跟 後半 list，每個 node val 應該要一樣

4. 如果都一樣，reverse 後半 list，復原 list

除了步驟有點巧妙，實作起來也是有點複雜：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == NULL or head->next == NULL) {
            return true;
        }

        // Find the middle of list
        ListNode* slow = head;
        ListNode* fast = head;

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

        // Reverse the second half of the list
        ListNode* second = reverse(slow->next);
        ListNode* copySecond = second; 

        // Compare two list
        ListNode* first = head;
        while(first != NULL and second != NULL) {
            if(first->val != second->val) {
                break;
            }

            first = first->next;
            second = second->next;
        }

        // Reverse the second list back
        reverse(copySecond);

        // After reversing, the second might be in the middle
        // So we use first or second == NULL to check
        if(first == NULL || second == NULL) {
            return true;
        }

        return false;
    }

private:
    ListNode* reverse(ListNode* head) {
        ListNode *prev = nullptr;

        while (head != nullptr) {
            ListNode *next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }

        return prev;
    }
};