Leetcode題解 Python：Palindrome Linked List

判別 Linked List 的值是否為回文。

凡是回文問題，就一定要知道長度，才能知道哪裡是分水嶺。

如果想用紀錄數值，最後再判別是否回文，由於該值可能為雙位數或是負數，如果想用 str 紀錄數值，就必須做特殊處理。

使用 list 紀錄，等過了分水嶺之後，就是該值與紀錄逐一對比，不符合就不是回文，找完就是回文。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head: return True
        len_head = 1
        SP = FP = head
        while FP.next:
            len_head += 1
            FP = FP.next            
        #
        stack = []
        for _ in range(len_head//2):
            stack.append(SP.val)
            SP = SP.next
        if len_head%2==1: SP = SP.next
        while stack:
            if SP.val != stack.pop():
                return False
            SP = SP.next
                
        return True

簡化回文的判斷，使用 stack == stack[::-1]，這樣只需要比較一次，不用記錄長度，空間複雜度仍是 O(n)。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:     
        stack = []
        while head:
            stack.append(head.val)
            head = head.next      
        return stack == stack[::-1]

如果利用循環的概念，快指針走 長度-1 、 慢指針走 1 ，兩兩相相比，不相等就不是，直到快指針追到慢指針結束。

但是這樣會超時。

如果空間複雜度局限於 O(1)，就要使用 reverse 的概念，不論是把分水嶺前面的或後面的 reverse 都可以。反序完再兩兩比較。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head: return True
        len_head = 1
        SP = FP = head
        while FP.next:
            len_head += 1
            FP = FP.next            
        #
        for _ in range(len_head//2):
            FP = SP
            SP = SP.next
            FP.next = head
            head = FP           
        if len_head%2==1: SP = SP.next
        while SP:
            if SP.val != head.val:
                return False
            SP = SP.next
            head = head.next
                
        return True

最近我的leetcode總是跑得比別人慢，即使是一樣的代碼，就是遜一節，不知道為什麼。