前言
簡單 √ 是反轉鏈表的衍生題，很快寫完了。不過沒考慮到恢復鏈表結構的問題。
題目
給你一個單鏈表的頭節點?head?，請你判斷該鏈表是否為回文鏈表。如果是，返回?true?；否則，返回?false?。
示例 1：
輸入：head = [1,2,2,1] 輸出：true
示例 2：
輸入：head = [1,2] 輸出：false
提示：
- 鏈表中節點數目在范圍
[1, 105]?內 0 <= Node.val <= 9
進階：你能否用?O(n)?時間復雜度和?O(1)?空間復雜度解決此題？
思路
一開始想著把鏈表直接反轉存儲，然后同時遍歷。但是考慮到題目要求的O（1）空間復雜度，想到可以只把前半部分，從中間開始向兩邊遍歷。如果鏈表長度為奇數，跳過最中間的那個數。
我的題解
/*** 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) {if (!head || !head->next){return true;}//鏈表長度ListNode* node = head;int count = 1;while (node->next){node = node->next;count++;}//反轉一半的鏈表，分奇偶兩種情況int len = count / 2;ListNode* pre = nullptr;ListNode* cur = head;while (len--){ListNode* nextnode = cur->next;cur->next = pre;pre = cur;cur = nextnode;}ListNode* left = pre;ListNode* right = cur;if (count % 2 != 0){right = right->next;}//左右同時開始遍歷while (left && right){if (left->val != right->val){return false;}left = left->next;right = right->next;}return true;}
};官方題解
將值復制到數組中后用雙指針法
- 復制鏈表值到數組列表中。
- 使用雙指針法判斷是否為回文。
class Solution {
public:bool isPalindrome(ListNode* head) {vector<int> vals;while (head != nullptr) {vals.emplace_back(head->val);head = head->next;}for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {if (vals[i] != vals[j]) {return false;}}return true;}
};快慢指針
- 找到前半部分鏈表的尾節點。
- 反轉后半部分鏈表。
- 判斷是否回文。
- 恢復鏈表。
- 返回結果。
跟筆者思路差不多，不過多了還原鏈表結構的步驟
class Solution {
public:bool isPalindrome(ListNode* head) {if (head == nullptr) {return true;}// 找到前半部分鏈表的尾節點并反轉后半部分鏈表ListNode* firstHalfEnd = endOfFirstHalf(head);ListNode* secondHalfStart = reverseList(firstHalfEnd->next);// 判斷是否回文ListNode* p1 = head;ListNode* p2 = secondHalfStart;bool result = true;while (result && p2 != nullptr) {if (p1->val != p2->val) {result = false;}p1 = p1->next;p2 = p2->next;} // 還原鏈表并返回結果firstHalfEnd->next = reverseList(secondHalfStart);return result;}ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;ListNode* curr = head;while (curr != nullptr) {ListNode* nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}return prev;}ListNode* endOfFirstHalf(ListNode* head) {ListNode* fast = head;ListNode* slow = head;while (fast->next != nullptr && fast->next->next != nullptr) {fast = fast->next->next;slow = slow->next;}return slow;}
};心得
有了反轉鏈表的基礎，思路就很快想到了。一半反轉，同時遍歷即可。但是筆者沒考慮到還原鏈表結構，這里暴露出筆者缺乏全局思考，代碼拓展性的問題，純粹是為了做題而做題，有點丟了本心，警醒！另外，反轉鏈表還有個缺點就是需要鎖定整個鏈表來解答，對于系統也不友好。最后，這里再加一個用棧的做法，比數組的做法更好，不過不是O（1）空間復雜度。
)
