原題鏈接：https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

目錄

1. 題目描述

2. 思路分析

3. 代碼實現

---

1. 題目描述

?

2. 思路分析

在做這道題之前，我們首先得知道什么是“回文”。

回文就是指正讀和反讀都相同的字符序列為“回文”，如“abba”、“abccba”、12321、123321是“回文”，“abcde”和“ababab”則不是“回文”。

知道了回文的意思后，我們開始分析題目！

先找到中間結點，然后把后半部分逆置，最后對前后兩部分一一比對，如果結點的值全部相同，則即為回文。否則就不是回文。

如果鏈表是回文結構如下圖（左半部分為奇數個結點的情況，右半部分為偶數個結點的情況）

如果有小伙伴不知道怎么求鏈表的中間結點，可以看看這篇文章：

https://blog.csdn.net/m0_62531913/article/details/132309395?spm=1001.2014.3001.5502

如果有小伙伴不知道怎么將鏈表逆置，可以看看這篇文章：

https://blog.csdn.net/m0_62531913/article/details/132297310?spm=1001.2014.3001.5502

3. 代碼實現

/*
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 *slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;}struct ListNode* reverseList(struct ListNode* head){struct ListNode *n1,*n2,*n3;n1=NULL;n2=head;if(n2)n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;}bool chkPalindrome(ListNode* head) {struct ListNode* mid=middleNode(head);struct ListNode* rmid=reverseList(mid);while(head&&rmid){if(head->val!=rmid->val){return false;}else{head=head->next;rmid=rmid->next;}}return true;}
};

?