描述.md

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

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

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

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

/**
 * 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) {
    
};

解法

双端队列法（不推荐）

1. 循环，把链表的值存入
2. 然后把值取出来判断即可

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    const deque = []
    while(head !== null) {
        deque.push(head.val)
        head = head.next
    }
    if (deque.length === 1) return true
    for (let i = 0, len = Math.floor(deque.length / 2); i < len; i++) {
        const prevVal = deque.shift()
        const endVal = deque.pop()
        if (prevVal !== endVal) {
            return false
        }
    }
    return true
};

栈

var isPalindrome = function(head) {
    const stack = []
    let temp = head
    while(temp !== null) {
        stack.push(temp.val)
        temp = temp.next
    }
    while(head !== null) {
        if (head.val !== stack.pop()) {
            return false
        }
        head = head.next
    }
    return true
};

这里相当于链表从前往后全部都比较了一遍，其实我们只需要拿链表的后半部分和前半部分比较即可，没必要全部比较，所以这里可以优化一下

var isPalindrome = function(head) {
    const stack = []
    let temp = head
    while(temp !== null) {
        stack.push(temp.val)
        temp = temp.next
    }
    let len = Math.floor(stack.length / 2)
    while(len -- >= 0) {
        if (head.val !== stack.pop()) {
            return false
        }
        head = head.next
    }
    return true
};

反转后半部分链表（用时最少，空间最小）

这题是让判断链表是否是回文链表，所谓的回文链表就是以链表中间为中心点两边对称。我们常见的有判断一个字符串是否是回文字符串，这个比较简单，可以使用两个指针，一个最左边一个最右边，两个指针同时往中间靠，判断所指的字符是否相等。

但这题判断的是链表，因为这里是单向链表，只能从前往后访问，不能从后往前访问，所以使用判断字符串的那种方式是行不通的。但我们可以通过找到链表的中间节点然后把链表后半部分反转），最后再用后半部分反转的链表和前半部分一个个比较即可。这里以示例2为例画个图看一下。

var isPalindrome = function(head) {
    let fast = head, slow = head;
    // 快的走两步，慢的走一半，最终慢的就走到一半
    while(fast !== null && fast.next !== null) {
        fast = fast.next.next
        slow = slow.next
    }
    // 反转后半部分
    slow = reverseList(slow)

    // 循环比较
    while(slow !== null) {
        if (head.val !== slow.val) {
            return false
        }
        slow = slow.next
        head = head.next
    }
    return true
};
// 反转链表
const reverseList = (head) => {
    let newList = null
    while(head) {
        const temp = head.next
        head.next = newList
        newList = head
        head = temp
    }
    return newList
}