javascript - 检查链表是否是回文

Question

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    if(head === null){
        return true;
    }
    var current, runner;
    current = head;
    runner = head;
    runner = reverseList(runner);
    while(current !== null && runner !== null){
        if(current.val != runner.val){
            return false;
        }
        else{
            current = current.next;
            runner = runner.next;
        }
    }
    return true;
};

这是我的反向函数。我认为这是我遇到最多问题的地方。我遇到了与this post类似的问题，但我不太确定如何解决对象引用问题。

var reverseList = function(head){
    var previous, current, next;
    current = head;
    previous = null;
    next = null;
    while(current !== null){
        next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    head = previous;
    return previous;
}

给出 [1, 3, 4, 5, 1] 的输入返回 true，所以我相信运行反向函数只会返回链表中的单个节点。

感谢任何帮助。

Answer 1

您的设置中有两个错误，我将向您指出...如果您想知道如何修复它们，我可以给您这些错误，但由于这看起来像是一个学习问题，所以我'我们只会为您指明正确的方向。

第一个错误确实在您的reverseList函数中，但不是因为它只返回单个节点。问题是您通过引用传递原始列表，然后对其进行操作，因此，当在reverseList runner 末尾时，如您所料包含 [1, 5, 4, 3, 1]，head 不再包含 [1, 3, 4, 5, 1]。您需要了解如何在不破坏初始列表的情况下生成反向列表...

其次，isPalindrome 内反转后的逻辑假设两个列表的长度相同，但如果一个列表仅仅是另一个列表的前缀，则返回 true (例如，如果 head 在您的操作后恰好只是 [1]，并且 runner 包含 [1, 5, 4, 3, 1])