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

快慢指针
快慢指针找中点，然后将后半段链表逆序；
时间复杂度：
空间复杂度：

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        ListNode *slow, *fast;
        slow = fast = head;
        while(fast != NULL && fast -> next != NULL){
            fast = fast -> next -> next;
            slow = slow -> next;
        }
        slow = reverseList(slow);
        fast = head;
        while(slow != NULL && fast != NULL){
            if(slow -> val != fast ->val) return false;
            slow = slow -> next;
            fast = fast -> next;
        }
        return true;
    }
    ListNode* reverseList(ListNode* head){
        ListNode* pre;
        while(head != NULL){
            ListNode* nxt = head -> next;
            head -> next = pre;
            pre = head;
            head = nxt;
        }
        return pre;
    }
};