Skip to content

回文链表

问题

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

 

示例 1


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


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

提示:

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

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

答案

js
var isPalindrome = function(head) {
    let cur = head;
    let dfs = (node)=>{
        if(node==null){
            return true;
        }
        let res = dfs(node.next)&&node.val==cur.val;
        cur = cur.next;
        return res;
    }
    return dfs(cur);
};
js
var isPalindrome = function(head) {
    let cur=head;
    let dfs=(node)=>{
        if(node==null) return true;
        return dfs(node.next)&&(node.val==cur.val)&&(cur=cur.next);
    }
    return dfs(cur);
};

扩展