题解 | #判断一个链表是否为回文结构#

1. 通过一快一慢两个指针fast和slow，fast走两步，slow走一步，遍历链表，寻找链表中点，翻转后半链表部分。完成翻转后，首尾同时向中间走，同时判断对应位置是否对应相等。
2. 遍历结束时，如果是奇数个结点，fast指向尾结点，slow指向中间结点，从slow->next开始翻转；如果是偶数个结点，fast指向null，slow指向后半部分的第一个结点，从slow开始翻转。所以只需判断fast为null即可确定从哪个结点mid开始翻转。
3. 翻转后得到后半部分链表的头结点end，此时mid->next已经为null了。end、head同时前进，判断结点值是否相等，或直至end为null。

分析：时间复杂度为O(n), 空间复杂度为O(1).

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    
    ListNode* reverseList(ListNode* head){
        if(head == nullptr or head->next == nullptr){
            return head;
        }
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur){
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        if(head == nullptr || head->next == nullptr){
            return true;
        }

        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* mid;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        mid = (!fast)?slow:slow->next;
        ListNode* end = reverseList(mid);
        while(end){
            if(end->val != head->val){
                return false;
            }
            end = end->next;
            head = head->next;
        }
        return true;
        
    }
};