鏈表的回文結構_牛客題霸_牛客網對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的算法，判斷其是否為。題目來自【牛客題霸】https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

題目

對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的算法，判斷其是否為回文結構。

給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結構。保證鏈表長度小于等于900。

測試樣例：

1->2->2->1

返回：true

?本題用到了鏈表的逆轉和鏈表的中間節點的應用

首先說一下鏈表的中間節點的查找

struct ListNode* midfind(struct ListNode* head)
{struct ListNode*fast,*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;}

?中間結點的查找主要運用到了快慢指針的遍歷。快指針比慢指針多走一步，最后快指針走到NULL，或者快指針的next為NULL停止。

再來說一下鏈表的逆轉

struct ListNode* reverselist(struct ListNode*head)
{struct ListNode*prve= NULL;struct ListNode*cur=head;while(cur){struct ListNode*next=cur->next;cur->next=prve;prve=cur;cur=next;}return prve;
}

逆轉的本質是要先定義一個空指針，如上代碼的*prve，然后下一步就開始保存cur的下一個指針，防止cur被覆蓋，導致下一個節點丟失。最后返回prve即可。原因是這是的cur已經指向NULL，所以無意義。

最后是實現鏈表回文（注意：C++兼容C語言）

#include <algorithm>
class PalindromeList {
public:struct ListNode* midfind(struct ListNode* head)
{struct ListNode*fast,*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;}
struct ListNode* reverselist(struct ListNode*head)
{struct ListNode*prve= NULL;struct ListNode*cur=head;while(cur){struct ListNode*next=cur->next;cur->next=prve;prve=cur;cur=next;}return prve;
}bool chkPalindrome(ListNode* A) {
struct ListNode* mid=midfind(A);
struct ListNode* revermid=reverselist(mid);
while(revermid&&A)
{if(revermid->val!=A->val){return false;
}
revermid=revermid->next;A=A->next;}return true;
}};