234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
    // 链表不能使用双指针，于是我们只能把原始链表反转再比较两者是否相同
    // 快慢指针，起初都指向表头，快指针一次走两步，慢指针一次走一步，遍历结束时：
    // 要么，slow 正好指向中间两个结点的后一个。
    // 要么，slow 正好指向中间结点。
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 判断奇偶,
    if (fast !== null) {
        // 说明链表长度为奇数
        slow = slow.next;
    }
    // 反转slow，再比较
    let left = head, right = reverse(slow);
    while (right !== null) {
        if (left.val !== right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }
    return true;
};
// 反转
const reverse = (head) => {
    let pre = null, cur = head;
    while (cur !== null) {
        let tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}