Palindrome Linked List

Palindrome Linked List

該題目的要求是判斷一個單鏈表是否是回文鏈表，題目的難度在於O(n)時間和O(1)空間的限制。

由於單鏈表不能反向訪問，所以不能直接通過原來的鏈表來判斷，解題的思路是首先對原來的鏈表的前半部分進行判斷，然後進行判斷（如鏈表為“12344321” 反轉之後為“43214321”）。想到這一點之後的實現就非常簡單了，完整的代碼如下所示：

class Solution {
public:
    ListNode* reverseHalf(ListNode* root){
        ListNode *fast = root, *slow = root;
//slow 指向要反轉的部分的後一個節點        
        while(fast != nullptr && fast -> next != nullptr){
            fast = fast -> next -> next;
            slow = slow -> next;
        }
        
        ListNode *h = new ListNode(0);
        h -> next = root;
//執行反轉
        ListNode *sec = root, *fir = root -> next;
        while(fir != slow){
            sec -> next = fir -> next;
            fir -> next = h -> next;
            h -> next = fir;
            fir = sec -> next;
        }
        return h -> next;
    }

    bool isPalindrome(ListNode* head) {
        int len = 0;
        ListNode* p = head;
        ListNode *fast, *slow;
//計算單鏈表的長度
        while(p != NULL){
            len++;
            p = p -> next;
        }
        if(len < 2)
            return true;
//反轉單鏈表的前半部分            
        ListNode* reversedList = reverseHalf(head);
//slow 指向單鏈表的中間位置
        fast = slow = reversedList;
        while(fast != nullptr && fast -> next != nullptr){
            fast = fast -> next -> next;
            slow = slow -> next;
        }
//fast 指向單鏈表的頭部
        fast = reversedList;
        if(len % 2 != 0)
            slow = slow -> next;
//判斷是否為回文子串
        while(slow  != nullptr){
            if(fast -> val != slow -> val)
                return false;
            fast = fast -> next;
            slow = slow -> next;
        }
        return true;
    }
};