234.回文链表

代码：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) return true;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != NULL && fast->next != NULL)//快慢指针
        {
            fast = fast->next;
            fast = fast->next;
            slow = slow->next;
        }
        auto n0 = slow;        
        auto n1 = n0->next;
        n0->next = NULL;
        ListNode* n2 = NULL;
        while(n1 != NULL)//逆序链表
        {
            n2 = n1->next;
            n1->next = n0;
            n0 = n1;
            n1 = n2;
        }
        auto temp = head;
        auto temp2 = n0;
        bool res = true;
        while(n0 != NULL && temp != NULL)//check
        {
            if(n0->val != temp-> val)
            {
                res = false;
                break;
            }
            n0 = n0->next;
            temp = temp->next;
        }
        n0 = NULL;
        n1 = temp2;
        while(n0 != slow)//恢复现场
        {
            n2 = n1->next;
            n1->next = n0;
            n0 = n1;
            n1 = n2;
        }
        return res;
    }
};

思路：
1.利用快慢指针找到链表的中间位置（或中间偏左）。
2.修改右半部分指针指向（反指），原慢指针指向空。
3.首尾遍历比较是否回文，若不回文，跳出循环
4.将链表复原

复杂度：
时间复杂度O(n)
空间复杂度O(1)