Palindrome Linked List

ListNode(val, next=None) is in the starter. Keep it.

Write is_palindrome(head) -> bool: True if the values of the singly linked list read the same from the front and from the back, False otherwise.

2 -> 5 -> 8 -> 5 -> 2    True

3 -> 1 -> 1 -> 3         True  (even length: no middle node)
4 -> 6 -> 4 -> 6         False (4 and 6 at the two ends don't match)
7                        True  (a single node)

• The list has between 1 and 100,000 nodes; values are digits 0 to 9.
• You may rearrange the list while you work; only the answer is checked.
• Copying the values into a Python list passes. For a better answer, use O(1) extra memory.

⭐ Bonus: a speed test with 100,000-node lists earns a star in O(n) time.