Leetcode 234. Palindrome Linked List

Palindrome Linked List

Palindrome Linked List : 判斷一個linked list它是否對稱

Python

方法一 :

先把數值放到一個list裡,接著判斷r[i] 和r[n-i-1] 是否相等,不相等返回False ,否則返回True

class Solution(object):
    def isPalindrome(self, head):

        if not head.next:
            return True
        l = [head.val]
        while head.next:
            head = head.next
            l.append(head.val)    #數值放到list
        n = len(l)
        for i in range(n//2):
            if l[i]!=l[n-i-1]:    #r[i] 和r[n-i-1] 是否相等
                return False
        return True

方法二 : 雙指針

利用雙指針從頭尾開始向內一個一個比較

class Solution(object):
    def isPalindrome(self, head):
    
        tmep = []
        while head:
            temp.append(head.val)    #數值放到list
            head = head.next 
        n = len(temp)
        left, right = 0, n - 1
        while left < right:
            if vals[left] != vals[right]:   #從頭尾開始向內一個一個比較
                return False
            left += 1             #左端向右
            right -= 1            #右端向左           
        return True

方法三 : 快慢指針

設立fast跟slow兩個指標,一個一次走兩步,一個一次走一步,直到fast走到底為止,此時可以發現slow會在linked list近中央的位置,將slow之後的linked list全數反轉(pre剛好會是反轉後的頭),這時我們只要一個指標從head開始,一個指標從pre開始,就能比較值來決定該linked list是否對稱了

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        fast=head
        slow=head
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
            
        pre=None
        while slow:
            temp=slow.next
            slow.next=pre
            pre=slow
            slow=temp
            
        l=head
        r=pre
        while r:
            if l.val!=r.val:
                return False
            l=l.next
            r=r.next
        return True

方法四 : 直接翻轉

def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        current_node = head
        while current_node is not None:
            vals.append(current_node.val)
            current_node = current_node.next
        return vals == vals[::-1]          #python翻轉方法

C++

雙指針法

1.遍歷鍊錶,將鍊錶中的元素依次存放到一個數組中。

2.使用雙指針法,比較數組的首尾元素是否相同,直到指針相遇或者不相同為止。

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

快慢指針法

1.使用快慢指針法找到鍊錶的中點,可以將鍊錶分為前半部分和後半部分。

2.反轉鍊錶的後半部分。

3.比較鍊錶的前半部分和後半部分是否相同。

4.恢復鍊錶的後半部分。

5.返回比較結果。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }
        ListNode* mid = getMid(head);
        ListNode* half = reverseList(mid->next);
        bool isPalindrome = true;
        ListNode* p1 = head;
        ListNode* p2 = half;
        while (isPalindrome && p2 != nullptr) {
            if (p1->val != p2->val) {
                isPalindrome = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        reverseList(half);
        return isPalindrome;
    }

    ListNode* getMid(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;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};