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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <clocale>
class PalindromeList {
public:
      struct ListNode* middleNode(ListNode* head)
      {
        struct ListNode* cur1 = head;
        if(cur1 == nullptr)
        {
             return nullptr;
        }
        int count = 0;//链表节点总数
        while(cur1 != nullptr)
        {
            count ++ ;
            cur1 =cur1->next;
        }
        int mid = count/2;
        while( mid > 0 )
        {
           head = head -> next;
           --mid;
        }
       return head;
      }

      struct ListNode* reverseList(ListNode* head)
      {
         if(head ==nullptr || head->next ==nullptr)
         {
           return head;
         }
         struct ListNode* hpre = nullptr;
         struct ListNode* hnext = nullptr;
       while(head)
       {
         hnext = head ->next;
         head ->next = hpre;
         hpre = head;
         head = hnext;
       }
       return hpre;
      }

    bool chkPalindrome(ListNode* head) {
        // write code here
      struct ListNode* mid = middleNode(head);
      struct ListNode* rhead = reverseList(mid);
      while(rhead)
      {
       if(head->val != rhead->val)
       {
        return false;
       }
          rhead = rhead->next;
          head = head->next;
      }
      return true;
    }
};