题目描述
题目链接：链表的回文结构_牛客题霸_牛客网 (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 here struct 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; } };
结果也就通过了：
