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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        typedef struct ListNode ListNode;
        // write code here
        //先逆置，再比较。
         //先快慢指针法找中点
         ListNode* slow=A;
         ListNode* fast=A;
        while(fast&&fast->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        //开始逆置
        ListNode* cur=slow,*head=slow;
        ListNode* pre=cur->next;
        cur->next=nullptr;
        while(pre){
            cur=pre;
            pre=pre->next;
            cur->next=head;
            head=cur;
        }
        //开始比较
        for(ListNode* a=A;cur;cur=cur->next,a=a->next){
            if(a->val!=cur->val){
                  return false;
            }
        }
        return true;
    }
};

先用快慢指针找到中点，再从中点开始让后半段逆置，接着就可以一个一个比较了。