检查回文链表

Question

我打算把原来的LinkedList反转过来和反转过来的对比一下。如果相同 return 为真。但是，我一直得到错误的结果。我哪里做错了？


var isPalindrome = function(head) {
    if(head == null || head.next == null) return true;
    
    let reversedHead = reverse(head)
    let count = 0
    while (head != null && reversedHead != null) {
        if(head.val != reversedHead.val) {
            return false
        }
        head = head.next
        reversedHead = reversedHead.next
    }
    if (head == null && reversedHead == null){
        return true
    } else {
        return false
    }
  
};
var reverse =(head)=> {
    let prev = null
    let next = new ListNode()
    let curr = new ListNode()
    curr = head
    while(curr){
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
}

Answer 1

调用后：

let reversedHead = reverse(head)

您将颠倒列表，即头部变成了尾部，尾部的下一个引用为空。因此你的循环将很快结束，如下所示：

head = head.next

...head 将是 null.

你需要重新考虑算法。有几种方法可以做到...

而不是 inplace 反转，你可以让 reverse return 一个完全 new 链表顺序相反：

function reverse(head) { // Does not modify the given list. Returns a new one.
    let node = head;
    let reversedHead = null;
    while (node) {
        reversedHead = new ListNode(node.val, reversedHead);
        node = node.next;
    }
    return reversedHead;
}

我在这里假设 ListNode 构造函数接受第二个参数：

class ListNode {
    constructor(val, next=null) {
        this.val = val;
        this.next = next;
    }
}

检查回文链表

Check Palindrome Linked List

javascript

algorithm

linked-list

palindrome