本系列博客为个人刷题思路分享，有需要借鉴即可。
1.题目链接：
2.详解思路：
思路：思路：先找到中间节点，然后逆置后半部分链表，一个指针指向链表的头节点，再一个指针指向逆置的头节点，一一进行比对。
本身这个题目时比较难的，所以先搞几个简单的相关题目铺垫一下
铺垫题目1：若需要见详解请单击：LINK
铺垫题目2：若需见详解，请单击：LINK
所以解决回文链表这道题要结合上面两道题目的代码：先找到中间节点再逆置，再比对。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ //找到中间结点 struct ListNode* middleNode(struct ListNode* head) { //思路2：快慢指针法 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) { //逆置链表为空 if(head == nullptr) return head; //不为空 struct ListNode* n1 = nullptr; struct ListNode* n2 = head; struct ListNode* n3 = head->next; while(n2) { //逆置 n2->next = n1; n1 = n2; n2 = n3; if(n3)//n3不为空 { n3 = n3->next; } } return n1; } class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code here //找到中间节点 struct ListNode* pMidNode = middleNode(A); //逆置中间节点及其以后的节点 struct ListNode* pNewMidNode = reverseList(pMidNode); //对比 while(A&&pNewMidNode) { if(pNewMidNode->val!=A->val) { return false; } //向后走 A = A->next; pNewMidNode = pNewMidNode->next; } return true; } };
完。
