Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Examples

Example 1

Input:  head = [1,2,2,1]
Output: true

Example 2

Input:  head = [1,2]
Output: false

Constraints

• The number of nodes in the list is in the range [1, 10^5]
• 0 <= Node.val <= 9

Follow up

Could you do it in O(n) time and O(1) space?

How the tests work: lists are written as arrays — [1,2,3] is the chain 1 → 2 → 3. Your function receives real ListNode objects.