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

Example 1:

``````Input: 1->2
Output: false``````

Example 2:

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

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

Analyze

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

``````第一步: 找中点, 分割链表;
q
s
dummy -> 1 -> 2 -> 2 -> 1 -> NULL
.
.
q
s
dummy -> 1 -> 2 -> 2 -> 1 -> NULL

left 链表:
1 -> 2 -> null

right 链表:
2 -> 1 -> null

left 链表:
1 -> 2 -> null

right 链表:
1 -> 2 -> null

``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @return {boolean}
*/
const dummy = new ListNode(0)

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

while (left && right) {
if (left.val !== right.val) {
return false
}
left = left.next
right = right.next
}
return true
}

const dummy = new ListNode(0)
dummy.next = list

let prev = null
let cur = dummy.next

while (cur) {
const next = cur.next
cur.next = prev
prev = cur
cur = next
}

return prev
}``````