234. 回文鏈表 - 力扣（LeetCode）https://leetcode.cn/problems/palindrome-linked-list/description/?envType=study-plan-v2&envId=top-100-liked

常規法

數組是連續的存儲空間，可以根據索引到達任意位置，鏈表只能一個個的順著指向訪問元素。最常規的方法就是將鏈表的元素用額外的空間存儲到列表里面，看這個列表是否是回文。

//c++
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {ListNode* a=head;vector<int> b;while(a){b.emplace_back(a->val);a=a->next;}for(int i=b.size()-1;i>-1;i--){if(head->val!=b[i])    return false;head=head->next;}return true;}
};#python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def isPalindrome(self, head: Optional[ListNode]) -> bool:a=[]while head:a.append(head.val)head=head.nextreturn a==a[::-1]

遞歸法

以一個全局變量記錄頭指針，然后遞歸到鏈表的最后，根據遞歸的性質不斷將頭指針的下一個元素與遞歸的上一層進行比較。

//c++
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {ListNode* frontPointer;
public:bool a(ListNode* b){if(b!=nullptr){if(!a(b->next))    return false;if(b->val!=frontPointer->val)   return false;frontPointer=frontPointer->next;}return true;}bool isPalindrome(ListNode* head) {frontPointer=head;return a(head);}
};#python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def isPalindrome(self, head: Optional[ListNode]) -> bool:self.front_pointer=headdef a(b=head):if b is not None:if not a(b.next):return Falseif self.front_pointer.val!=b.val:return Falseself.front_pointer=self.front_pointer.nextreturn Truereturn a()

改變鏈表

不用額外的空間，但又想判斷鏈表，所以一次走一步，一次走兩步找到中間位置（挺巧妙的），然后將中間位置往后的鏈表反轉，直接訪問元素進行判斷，最后要注意恢復鏈表。

//c++
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* a(ListNode* b){ListNode* pre=nullptr;while(b){ListNode* nex=b->next;b->next=pre;pre=b;b=nex;}return pre;}bool isPalindrome(ListNode* head) {ListNode* f=head;ListNode* s=head;while(f->next&&f->next->next){f=f->next->next;s=s->next;}s=a(s);f=s;bool ans=true;while(head&&s){if(head->val!=s->val)   ans=false;head=head->next;s=s->next;}a(f);return ans;}
};#python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def isPalindrome(self, head: Optional[ListNode]) -> bool:if not head:return Truef=heads=headwhile f.next and f.next.next:f=f.next.nexts=s.nexta=self.reverse(s)b=aans=Truewhile head and a:if head.val!=a.val:ans=Falsehead=head.nexta=a.nextself.reverse(b)return ansdef reverse(self,head):pre=Nonec=headwhile c:n=c.nextc.next=prepre=c c=nreturn pre