0、题目描述

链表回文结构

1、法1

一个复杂的问题可以拆解成几个简单的问题，找中间节点和逆置链表（翻转链表）之前都做过。

class PalindromeList {
public://1、找中间节点ListNode* FindMid(ListNode* A){if (A == nullptr || A->next == nullptr){return A;}ListNode* fast = A;ListNode* slow = A;while (fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;}//2、翻转链表ListNode* ReverseList(ListNode* phead){ListNode* cur = phead;ListNode* newhead = nullptr;while (cur){ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;}return newhead;}bool chkPalindrome(ListNode* A) {   ListNode* mid = FindMid(A);ListNode* B = ReverseList(mid);//3、依次比对while (A && B){if (A->val != B->val){return false;}A = A->next;B = B->next;}return true;}
};