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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <algorithm>
#include <cstddef>
class PalindromeList {
  public:

    struct ListNode* reverse(struct ListNode* head) {
        struct ListNode* newHead = NULL;
        struct ListNode* pcur = head;
        while (pcur) {
            struct ListNode* next = pcur->next;//建议画图理解，类似于头插
            pcur->next = newHead;
            newHead = pcur;
            pcur =  next;
        }
        return newHead;
    }

    struct ListNode* find(struct ListNode* head)//利用的快慢指针
    {
        struct ListNode* fast=head;
        struct ListNode* slow=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;//fase一次走两步
            slow=slow->next;//slow一次走一步
        }
        return slow;//到最后fast走过的路程是slow走过的路程的两倍，slow自然是中点(偶数中点为用两个中间值其中的靠后的那个)
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid = find(A);//find函数找到链表的中间值返回给mid
        mid = reverse(mid);//reverse函数把mid为头节点的新链表逆置，再把逆置过后的指针返回给mid
        while(mid)
        {
            if(A->val!=mid->val)//判断二者是否相等，若不相等，则返回false
            {
                return false;
            }
            mid=mid->next;//mid 和 A 往后走(可以定义pcur来代替A遍历，防止改变原链表）
            A=A->next;
        }
        return true;//遍历完后，若都相等则返回true

    }
};