链表的回文结构

题目描述

题目链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

题目分析

我们的思路是：

• 找到中间结点
• 逆置后半段
• 比对

我们可以简单画个图来表示一下：

 ‘

奇数和偶数都是可以的

找中间结点

我们可以用快慢指针来找中：leetcode：链表的中间结点-CSDN博客

写一个找中的函数middleNode：

然后写一个逆置的函数reverseList：

我们画图表示一下头插的过程：

最后我们进行一个对比

代码示例

有了这个思路，我们就可以编写代码了：

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:struct ListNode*reverseList(ListNode*head){struct ListNode*cur=head;struct ListNode*newhead=NULL;while(cur){struct ListNode*next=cur->next;//头插cur->next=newhead;newhead=cur;cur=next;}return newhead;}struct ListNode*middleNode(ListNode*head){struct ListNode*slow,*fast;slow=fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;}bool chkPalindrome(ListNode* head) {// write code herestruct ListNode*mid=middleNode(head);struct ListNode*rhead=reverseList(mid);while(head&&rhead){if(head->val!=rhead->val){return false;}head=head->next;rhead=rhead->next;}return true;}
};

结果也就通过了：