题解 | #链表的回文结构#

两种方法，第二种的话空间复杂度成O(N)了；；

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        if(A==NULL)
            return false;
        ListNode* slow=A,*fast=A;
        while(fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode* cur=NULL,*next=slow;
        while(slow){
            next=slow->next;
            slow->next=cur;
            cur=slow;
            slow=next;
        }
        next=A;
        while(cur){
            if(next->val!=cur->val)
                return false;
            next=next->next;
            cur=cur->next;
        }
        return true;



        // write code here
//         if(A==NULL)
//             return false;
//         ListNode* cur=A;
//         vector<int> v;
//         while(cur){
//             v.push_back(cur->val);
//             cur=cur->next;
//         }
//         for(int i=0;i<v.size()/2;i++){
//             if(v[i]!=v[v.size()-i-1])
//                 return false;
//         }
//         return true;
    }
};