【刷题记录】链表的回文结构

本文主要是介绍【刷题记录】链表的回文结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本系列博客为个人刷题思路分享，有需要借鉴即可。

1.题目链接：
LINK
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;}
};