本題來自鏈表的回文結構_牛客題霸_牛客網 (nowcoder.com)

234. 回文鏈表 - 力扣（LeetCode）

題面：

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

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

測試樣例：1->2->2->1

返回：true

思路：

方法一：

對于數組來說，可以先獲取數組的大小，然后從兩端向中間比較數值，本題給了鏈表的最大長度，因此可以先創建900大小的數組，讀取鏈表的值給數組

方法二：

先找遍歷一次，找鏈表的中間節點，也就是后一半鏈表的起始節點，然后給鏈表后半段逆置一下，再從頭，和這個新起始節點依次比較，彈出條件是這兩個指針指向的節點的值不相等，循環條件是后半段結束（偶數個節點，正好結束），或者即將結束(奇數個節點，最后一個節點自己對稱自己，不用比較這個節點)

在這里用到了兩個函數（自己做過的題）。一個是找鏈表的中點，一個是逆置鏈表?縫合怪

找中點的簡單題 鏈表的中間節點-CSDN博客

逆置鏈表的簡單題 反轉鏈表-CSDN博客

代碼：

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/class PalindromeList {
public:
typedef struct ListNode node;struct ListNode* middleNode(struct ListNode* head) // 找中間{// 雙指針——快慢指針法node* slow = head;node* fast = head;while (fast && fast->next)//當快指針到尾，或者快到尾都算結束{fast = fast->next->next;// 快指針一次走兩步slow = slow->next;// 慢指針一次走一步}return slow;
}
struct ListNode* reverseList(struct ListNode* head) // 逆置
{if (head == NULL && head->next == NULL)return head;struct ListNode* n1, * n2, * n3;n1 = head;n2 = n1->next;n3 = n2->next;n1->next = NULL;while (1){n2->next = n1;n1 = n2;n2 = n3;if (n2 == NULL)break;n3 = n3->next;}return n1;
}bool chkPalindrome(ListNode* A) {// write code herenode*list2=middleNode(A);list2=reverseList(list2);while(list2&&list2->next){if(A->val!=list2->val)return false;A=A->next;list2=list2->next;}return true;}
};

總結：

單鏈表的缺陷就是不能訪問上一個節點，因此直接逆置后半段，來模擬倒著訪問節點