題目描述

題目鏈接：鏈表的回文結構_牛客題霸_牛客網 (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;}
};

結果也就通過了：