LeetCode 234 – Python 3 (Week 3 – 07)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        
        #if head == None: return False 
        #if[], output should be true
        
        #fist-find the middle node, second-reverse half of the list, third-compare
        fast = slow = head
        pre = None      
        while fast and fast.next: #make sure fast is the last one or None.
            fast = fast.next.next
            slow = slow.next          
            head.next = pre
            pre = head
            head = slow
            
        
        #1-2-3-4, now slow is 3, fast is null, pre is 2
        #1-2-3-4-5, slow is 3, fast is 5, pre is 2      
        if fast: slow = slow.next #slow is 4
            
                        
        #compare
        while pre and slow:
            if pre.val != slow.val:
                return False
            else:
                pre = pre.next
                slow = slow.next
        
        return True