Palindrome Linked List

You get the head of a singly linked list. Each node holds a digit.

Return true if the values read the same forward and backward. Otherwise, return false.

 

Example 1:

Input: head = [5,1,8,1,5]
Output: true
Explanation: Read backward, it is still 5, 1, 8, 1, 5.
The middle 8 has no partner. That's fine.

Example 2:

Input: head = [2,6,6,9]
Output: false
Explanation: The first value is 2 but the last one is 9.

Example 3:

Input: head = [7]
Output: true
Explanation: A single node reads the same both ways.

 

Constraints:

• 1 to 100,000 nodes.
• Each value is a digit from 0 to 9.

 

Follow up: This lesson's solution copies the values. That takes O(n) extra space. A recursive version uses the call stack the same way. As an extra challenge, can you check the list in O(n) time and O(1) extra space?