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

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    ListNode* reverse(ListNode* head){
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    bool isPail(ListNode* head) {
        // write code here
        ListNode* slow = head;
        ListNode* fast = head;
        
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        
        // 如果fast不为空，说明链表共奇数个节点，否则说明偶数
        if(fast)
            slow = slow->next;
        
        ListNode* ptr1 = head;
        ListNode* ptr2;
        ptr2 = reverse(slow);
        while(ptr2){
            if(ptr2->val != ptr1->val)
                return false;
            ptr2 = ptr2->next;
            ptr1 = ptr1->next;
        }
        return true;
    }
};