LeetCode 234. 回文链表（快慢指针+链表反转）

示例 1:
输入: 1->2
输出: false

示例 2:
输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next)
        	return true;
        ListNode *fast = head, *slow = head, *prev = NULL, *nextNode = NULL;
        //之前没初始化prev，报错了，链表一定注意不要对未知的指针操作
        while(fast && fast->next)
        {
        	fast = fast->next->next;
        	nextNode = slow->next;
        	slow->next = prev;
        	prev = slow;
        	slow = nextNode;
        }
        if(fast != NULL)//奇数个节点情况
        	slow = slow->next;
        while(slow)
        {
        	if(prev->val != slow->val)
        		return false;
        	prev = prev->next;
        	slow = slow->next;
        }
        return true;
    }
};