145. Palindrome Linked List

Easy · Linked List

Given a singly linked list, determine if it is a palindrome. A palindrome reads the same forwards and backwards.

You must solve this problem in O(n) time complexity and O(1) space complexity (excluding the space needed to store the output).

Examples

Example 1
Input: [1, 2, 2, 1]
Output: true
Explanation: The list reads the same forwards and backwards: 1→2→2→1.
Example 2
Input: [1, 2, 3, 2, 1]
Output: true
Explanation: The list is a palindrome with an odd length: 1→2→3→2→1.

Constraints