LeetCode 234 Palindrome Linked List：O(n) 時間 O(1) 空間判斷鏈表回文

題目大意

給定單鏈表頭節點，判斷是否為回文結構。要求 O(n) 時間、O(1) 空間。

快慢指針 + 就地逆序後半部

1. 找中點：快指針每次 2 步，慢指針每次 1 步。快指針到達末尾時，慢指針在中點（奇數長度）或偏右中點（偶數長度）。
2. 逆序後半部：從慢指針位置開始，就地逆序鏈表。
3. 比較：雙指針分別從頭、逆序後的後半部頭部出發，逐節點比較值。
4. 恢復（可選）：再次逆序後半部掛回原鏈表，保持不修改輸入結構。

C++ 實現

bool isPalindrome(ListNode* head) {
    vector v;
    for (ListNode* p=head; p; p=p->next) v.push_back(p->val);
    for (int i=0, j=v.size()-1; i

複雜度

版本
時間
空間
修改輸入
Vector
O(n)
O(n)
否
就地逆序
O(n)
O(1)
臨時修改，可恢復