求star

题目#

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

示例 1：

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

示例 2：

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

提示：

• 链表中节点数目在范围[1, 105] 内

• 0 <= Node.val <= 9

解题:key:#

① 复制到数组中然后双端遍历#

/**
 * 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) {
    const arr = []
    while(head) {
        arr.push(head.val)
        head = head.next
    }
    for(let i=0,j=arr.length-1;i<j;i++,j--){
        if(arr[i] !== arr[j]){
            return false
        }
    }
    return true
};

② 递归(原理还是双指针)#

TIP

​ currentNode 指针是先到尾节点，由于递归的特性再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val != frontPointer.val 则返回 false。反之，frontPointer 向前移动并返回 true。

​ 递归处理节点的顺序是相反的，而我们在函数外又记录了一个变量，因此从本质上，我们同时在正向和逆向迭代匹配。

/**
 * 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}
 */

let frontPointer 
var check = (currentNode) => {
    if(currentNode !== null){
        if(!check(currentNode.next)){
            return false
        }
        if(currentNode.val !== frontPointer.val){
            return false
        }
        frontPointer = frontPointer.next
    }
    return true
}
var isPalindrome = function(head) {
    frontPointer = head
    return check(head)
};