[数据结构与算法]leetcode 234 回文链表 空间优化

说是个简单题，做起来是真费劲。正常做也没啥事，题目非要要求O(1)空间，就很难受了。

做法：反转后面那部分链表，然后用两个指针比较即可。

难点一：找到链表中间
由于我们要预存链表中间位置，所以分奇数偶数两种情况讨论，用快慢指针找到中间即可。

难点二：反转链表
反转链表需要存两个指针：前指针和当前指针，每次要处理好这两个的关系，这样当next为空时所有的节点都反转完成。

/**
 * 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) {
        if(!head || !head->next)return true;

        ListNode *slow = head, *fast = head->next;
        while(fast->next)
        {
            slow = slow->next;
            fast = fast->next;
            if(!fast || !fast->next)break;
            fast = fast->next;
        }

        ListNode *sec = slow->next;

        if(sec && sec->next)
        {
            ListNode *pre = sec, *curr = sec->next, *tmp;

            while(curr)
            {
                tmp = curr;
                curr = curr->next;
                tmp->next = pre;
                pre = tmp;
            }
            slow->next = pre;
            sec->next = nullptr;
        }

        sec = slow->next;
        ListNode *fir = head;
        while(sec)
        {
            if(sec->val != fir->val)return 0;
            sec = sec->next;
            fir = fir->next;
        }

        return 1;
    }
};