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

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

class PalindromeList {
public:
    typedef struct ListNode ListNode;

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

    }

    ListNode* reverse(ListNode* mid)
    {
        ListNode* m1 = NULL;
        ListNode* m2 = mid;
        ListNode* m3 = mid->next;
        while(m3)
        {
            m2->next = m1;
            m1 = m2;
            m2 = m3;
            m3 = m3->next;
        }
        return m2;

    }

    bool chkPalindrome(ListNode* A) {
        
        ListNode* mid = findnode(A);
        ListNode* rmid = reverse(mid);
        while(rmid && A)
        {
            if(rmid ->val != A->val)
            {
                return false;
            }
            rmid = rmid->next;
            A = A->next;
        }
        return true;

    }
};