Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2Output: false

Example 2:

Input: 1->2->2->1Output: true

Follow up: Could you do it in O(n) time and O(1) space?

Analyze

1. 第一步: 使用快慢指针找到链表中点, 链表分割为左右两部分;
2. 第二步: 翻转右边的链表节点;
3. 第三步: 比较左右两边的节点;

第一步: 找中点, 分割链表;                        q              sdummy -> 1 -> 2 -> 2 -> 1 -> NULL              .              .                        q              sdummy -> 1 -> 2 -> 2 -> 1 -> NULL
left 链表:1 -> 2 -> null
right 链表:2 -> 1 -> null

left 链表:1 -> 2 -> null
right 链表:1 -> 2 -> null

/** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} head * @return {boolean} */var isPalindrome = function(head) {  const dummy = new ListNode(0)  dummy.next = head
let slow = dummy, quick = dummy  while (quick && quick.next) {    slow = slow.next    quick = quick.next.next  }
let right = slow.next  slow.next = null  let left = dummy.next
return prev}