動機

可以去看143 重點是找中點時判斷長度的奇偶姓!!

Problem

Given the head of a singly linked list, return true if it is a palindrome.

 

Example 1:

Input: head = [1,2,2,1]Output: true

Example 2:

Input: head = [1,2]Output: false

 

Constraints:

  • The number of nodes in the list is in the range [1, 105].
  • 0 <= Node.val <= 9

 

Follow up: Could you do it in O(n) time and O(1) space?

Sol

找中點，reverse，compare

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head.next:
            return True
        # mid
        mid,b = head,head
        while b.next and b.next.next:
            mid,b = mid.next,b.next.next
        right = mid.next
        # 1,2     b.n.n is None
        # 1,2,3   b.n is None
        # 1,2,3,4 b.n.n is None
        isodd = (b.next is None)
        
        # rev right
        now, nextN = right, right.next
        while nextN:
            tmp = nextN.next
            nextN.next = now
            now, nextN = nextN, tmp
        right.next = None
        right = now
        mid.next = right
        
        leftEnd = mid if isodd else right

        # comp
        while head != leftEnd:
            if head.val != right.val:
                return False
            head, right = head.next, right.next
        return True