[LeetCode] 234. Palindrome Linke

这题的进阶要求是O(n)的时间复杂度和O(1)的空间复杂度，意味着包括栈和字符串在内的所有开辟数组的解决方案都不可行。于是采用这样的解决方案：

1. 找到链表中点
2. 翻转链表后半部分
3. 比较前后两段链表是否相等

这样，本题就拆解成了 Middle of the Linked List 和 Reverse Linked List 两个问题。把reverseList(ListNode* head)改成非递归可能还会有更低的时间复杂度。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return p;
    }
    ListNode* findMiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
public:
    bool isPalindrome(ListNode* head) {
        // trivial case
        if (head == nullptr || head->next == nullptr) {
            return true;
        }

        // nontrivial case
        ListNode* mid = findMiddle(head);
        ListNode* r = reverseList(mid);
        // You got this after reversing the list:
        //   1  ->  2  ->  2  <-  1
        // head                   r
        while (r != nullptr) {
            if (r->val != head->val) {
                return false;
            }
            r = r->next;
            head = head->next;
        }
        return true;
    }
};