"""
Exercise 2: Palindrome Linked List (LeetCode 234)

Return True if the list reads the same forwards and backwards in O(n) time
and O(1) extra space: find the middle, reverse the second half, compare.
"""

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def is_palindrome(head):
    # TODO
    return False


# --- self-check: do not modify below this line ---
def build(vals):
    dummy = cur = ListNode()
    for v in vals:
        cur.next = ListNode(v); cur = cur.next
    return dummy.next

cases = [([1, 2, 2, 1], True), ([1, 2], False), ([1], True), ([1, 2, 3, 2, 1], True), ([1, 2, 3, 1], False)]
ok = True
for vals, want in cases:
    got = is_palindrome(build(vals))
    print(vals, "->", got)
    ok = ok and got == want
print("PASS" if ok else "FAIL")