链表刷题|判断回文结构

题目来自于牛客网，本文章仅记录学习过程的做题理解，便于梳理思路和复习

我做题喜欢先把时间复杂度和空间复杂度放一边，先得有大概的解决方案，最后如果时间或者空间超了再去优化即可。

思路一：要判断是否为回文结构则要对比链表左半部分和右半部分是否相等，由于链表的单向移动的特性，显然不太好操作，第一时间想到的是将其先遍历存入到数组当中，存入到数组后就可以很方便的操作了，大家都学过的从数组的首末两端分别往中间边移动边比较即可，期间有一次数据比对不一致都可以直接return返回false了，反之如果移动比对到了中间就说明是回文结构。

思路一终归有些局限，如果没有给定范围限制的话就不行了，所以我么尽量还是尝试尝试别的方法

思路二：先将链表分成两半（也就是先找中间节点），然后再将后半部分的链表反转一下，接着分别遍历比较两个链表即可。

老师说过我们做题的时候想不到这些方法很正常，学习是不断积累的，随着我们做的题多了，我们能想到使用的方法自然也就多了

class PalindromeList{
public://反转链表ListNode* middleNode(struct ListNode* head){//定义快慢指针ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}//找中间节点 ListNode* reverseList(struct ListNode* head){if (head == NULL){return head;}ListNode* n1, * n2, * n3;n1 = NULL, n2 = head, n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;}bool chkPalindrome(ListNode* A){//找中间节点ListNode* mid = middleNode(A);//反转以中间节点为头的链表ListNode* right = reverseList(mid);ListNode* left = A;//遍历原链表和反转链表，挨个比较值是否相等while (right){if (left->val != right->val){return false;}left = left->next;right = right->next;}return true;}
};