Leetcode 234: Palindrome Linked List - Python

linkedListPalindrome.py

def isPalindrome(head):
    if head == None or head.next == None:
        return True

    # find mid
    mid, fast = head, head
    prevOfMid = None

    while fast and fast.next:
        prevOfMid = mid
        mid = mid.next
        fast = fast.next.next

    # break into two half
    prevOfMid.next = None

    # reverse right half
    cur = mid
    prev = None

    while cur:
        nex = cur.next
        cur.next = prev
        prev = cur
        cur = nex

    # compare two half for palindrome
    p1 = head
    p2 = prev

    while p1 and p2:
        if p1.val != p2.val:
            return False
        p1 = p1.next
        p2 = p2.next

    return True