Palindrome Linked List
You are given the head of a singly linked list. Return true if its values read the same from front to back as from back to front, and false otherwise.
The list only links forward, so you can't walk it backwards directly. Copying the values into an array works; try to solve it in O(n) time with O(1) extra space. You may rewire the list's next pointers while you work.
Constraints
- The list has between
1and10^5nodes. 0 <= Node.val <= 9
Examples
Example 1
Input: head = [1,2,2,1] Output: true
Read backwards the values are 1, 2, 2, 1 again.
Example 2
Input: head = [1,2] Output: false
Backwards it reads 2, 1.
Example 3
Input: head = [1,2,3,2,1] Output: true
With an odd length the middle value (3) pairs with itself and doesn't need a partner.
JavaScript you'll use: Linked list and tree nodes
/**
* Linked list nodes are provided (you don't need to define them):
* class ListNode { constructor(val = 0, next = null) { this.val = val; this.next = next; } }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
function isPalindrome(head) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.