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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    ListNode*findMid(ListNode*phead)
    {
        //应用快慢指针
        ListNode*slow=phead,*fast=phead;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
    ListNode*revese(ListNode*phead)
    {
        //采用三指针法
        ListNode*n1=NULL,*n2=phead,*n3=n2->next;
        while(n2)
        {
            n2->next=n1;
            n1=n2;
            n2=n3;
            if(n3)
            n3=n3->next;
        }
        return n1;
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        //先找中间节点，从中间节点开始到末尾进行反转链表，然后把这两个分割开的链表进行比较

        //找中间节点
        ListNode*mid=findMid(A);
        //反转链表
        ListNode*rhead=revese(mid);
        ListNode*pcur=A;
        while(rhead)
        {
            if(pcur->val!=rhead->val)
                return false;
            pcur=pcur->next;
            rhead=rhead->next;
        }
        return true;
    }
};