"""
Exercise 1: Middle of the Linked List (LeetCode 876)

Return the middle node (the second middle if the length is even) using fast
and slow pointers. The self-check builds lists for you and compares values.

  1->2->3->4->5      -> node 3
  1->2->3->4->5->6   -> node 4
"""

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

def middle_node(head):
    # TODO
    return head


# --- 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

ok = True
for vals, want in [([1, 2, 3, 4, 5], 3), ([1, 2, 3, 4, 5, 6], 4), ([1], 1), ([1, 2], 2)]:
    got = middle_node(build(vals)).val
    print(vals, "->", got)
    ok = ok and got == want
print("PASS" if ok else "FAIL")