回文链表 2022-03-05 周六

题目

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

示例 1：

image

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

示例 2：

image

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

力扣官方解法

思路

• 将单链表转化为数组

• 用双指针法检查是否回文

JS代码

/**
 * 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) {
    // 将链表中的值复制到一个数组中
    // 用一个指针代替head移动，保持head不变
    let values = [];
    let current = head;
    while(current != null) {
        values.push(current.val);
        current = current.next;
    }

    // 用双指针法检查数组是否回文
    for(let i=0, j=(values.length-1); i<j; i++, j--) {
        if (values[i] != values[j]) {
            return false;
        }
    }

    return true;
};

备注

• 递归法更适合二叉树，链表问题还是遍历或者转化为指针比较好；

• 逆序链表法有点复杂，还是数组双指针法好理解一点；