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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

class PalindromeList 
{
public:

struct ListNode* FindMid(struct ListNode* A)
{
    struct ListNode* fast = A;
    struct ListNode* slow = A;
    while(fast&&fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;  
}

struct ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    struct ListNode* pf1 = NULL;
    struct ListNode* pf2 = head;
    struct ListNode* pf3 = pf2->next;
    while(pf2->next)
    {
        pf2->next = pf1;
        pf1 = pf2;
        pf2 = pf3;
        pf3 = pf3->next;
    }
    pf2->next = pf1;
    pf1 = pf2;
    return pf1;
}

    bool chkPalindrome(ListNode* A) 
    {
        struct ListNode* mid = FindMid(A);
        struct ListNode* cur = reverseList(mid);
        while(A&&cur)
        {
            if(A->val!=cur->val)
            {
                return false;
            }
            A = A->next;
            cur = cur->next;
        }
        return true;
    }
};