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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
  public:
//利用快慢指针寻找中间结点
    struct ListNode* middleNode(struct ListNode* head) {
        struct ListNode* fast = head;
        struct ListNode* slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
//将链表逆序，链表的指向倒置
    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* cur = head;
        struct ListNode* tail = NULL;
        while (cur) {
            struct ListNode* next = cur->next;
            cur->next = tail;
            tail = cur;
            cur = next;
        }
        return tail;
    }

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