LeetCode Algorithm 劍指 Offer II 027. 回文連結清單

題目連結：​​劍指 Offer II 027. 回文連結清單​​

Ideas

算法：雙指針

資料結構：連結清單

思路：首先把連結清單的後半段翻轉過來，然後用兩個指針分别從頭和從中間開始周遊判斷是否相同，如果相同則是回文連結清單，否則不是回文連結清單，但不管是不是回文連結清單，翻轉的連結清單還是要翻轉回去。

1.用快慢指針，快指針quick一次走兩步，慢指針slow一次走一步，當快指針到頭時，慢指針正好到連結清單中間；（如果連結清單長度為奇數，快指針最終走到最後一個元素，如果連結清單長度為偶數，快指針最終走到倒數第二個元素）

2.從連結清單中間開始，将後面的節點逐個翻轉，即目前節點原本指向下一個節點，改為指向前一個節點；

3.雙指針分别從連結清單的頭尾出發，周遊判斷目前節點值是否相等，最終雙指針相遇時截止；

4.從連結清單中間開始，再将後面的節點翻轉回去。

Code

C++

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }
        // 1.快慢指針找到連結清單中間位置
        ListNode *quick = head, *slow = head;
        while (quick->next != nullptr && quick->next->next != nullptr) {
            slow = slow->next;
            quick = quick->next->next;
        }
        // 2.從連結清單中間位置開始将後續節點翻轉
        ListNode *cur = slow->next;
        slow->next = nullptr;
        while (cur != nullptr) {
            ListNode *nxt = cur->next;
            cur->next = slow;
            slow = cur;
            cur = nxt;
        }
        // 3.雙指針分别從頭尾開始周遊
        bool res = true;
        quick = head;
        ListNode *tail = slow;
        while (quick != nullptr && slow != nullptr) {
            if (quick->val != slow->val) {
                res = false;
                break;
            }
            quick = quick->next;
            slow = slow->next;
        }
        // 4.将翻轉的節點再翻轉回去
        cur = tail->next;
        tail->next = nullptr;
        while (cur != nullptr) {
            ListNode *nxt = cur->next;
            cur->next = tail;
            tail = cur;
            cur = nxt;
        }
        return res;
    }
};      

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> values;
        while (head) {
            values.push_back(head->val);
            head = head->next;
        }
        for (int i = 0, j = values.size() - 1; i < j; i++, j--) {
            if (values[i] != values[j]) {
                return false;
            }
        }
        return true;
    }
};      

Python

class Solution:
    def findFirstHalfEnd(self, node):
        fast = slow = node
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverseList(self, node):
        previous, current = None, node
        while current is not None:
            nextNode = current.next
            current.next = previous
            previous = current
            current = nextNode
        return previous

    def isPalindrome(self, head: ListNode) -> bool:
        # 判斷邊界情況
        if head is None:
            return True

        # 找到前半部分連結清單的為節點并反轉後半部分連結清單
        firstHalfEnd = self.findFirstHalfEnd(head)
        secondHalfStart = self.reverseList(firstHalfEnd.next)

        # 判斷是否為回文
        ans, firstPosition, secondPosition = True, head, secondHalfStart
        while ans and secondPosition is not None:
            if firstPosition.val != secondPosition.val:
                return False
            firstPosition = firstPosition.next
            secondPosition = secondPosition.next

        # 還原反轉的連結清單
        firstHalfEnd.next = self.reverseList(secondHalfStart)

        return ans