307. Check if Linked List is a Palindrome

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

A palindrome reads the same forwards and backwards. Aim for O(n) time and O(1) space by reversing the second half in-place.

Input: Head of a singly linked list.

Output: Boolean true if palindrome, false otherwise.

Examples

Input: [1,2,2,1]
Output: true
Explanation: Find middle using slow/fast: slow stops at second 2.
Reverse second half [2,1] → [1,2].
Compare first half [1,2] with reversed [1,2]: equal → palindrome.

Input: [1,2]
Output: false
Explanation: First half [1], second half [2]. 1 ≠ 2. Not palindrome.

Input: [1,2,3,2,1]
Output: true
Explanation: Middle=3. First half [1,2,3], second half reversed [1,2,3]. Equal → palindrome.

Constraints

• 1 <= number of nodes <= 10^5
• 0 <= Node.val <= 9

Asked by