Palindrome Linked List

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

You must solve it in O(n) time and O(1) space.

Examples

Example 1:

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

Output: true

Explanation: The values read the same forwards and backwards: 1 → 2 → 2 → 1.

Example 2:

Input: head = [1,2]

Output: false

Explanation: The values read 1 → 2 forwards but 2 → 1 backwards — not a palindrome.

Example 3:

Input: head = [1]

Output: true

Explanation: A single-element list is always a palindrome.

Constraints

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