时间戳

首页 > 解决方案 > 在 JavaScript 中检查链表是否为回文

javascript - 在 JavaScript 中检查链表是否为回文

问题描述

我在 JavaScript 中编写了以下函数来检查单链表是否是回文。但是，我在 10 次测试中有 2 次失败，我不知道为什么。

这是我正在下降的测试。

  1. l: [0, 1, 0]
  2. l: [1, 1000000000, -1000000000, -1000000000, 1000000000, 1]

对于回文，两者都应该返回 true，但我的函数返回 false。

这是我的代码：


    function isListPalindrome(l) {
    let curr = l;
    let arr = [];
    
    if (l == null)
        return true;
    
    // push all elements of l into the stack.
    // a stack in JS is an array.
    while(curr != null){
        arr.push(l.value);
        
        // move ahead:
        curr = curr.next;
    }
    
    let curr2 = l;
    // Traverse the list again & check by popping from the stack:
    while(curr2 != null){
        
        // get the top most element on the stack:
        let num = arr.shift();
        
        // check if the node data isn't the same as the element popped:
        if (curr2.value != num){
            return false;
        }
        
        // move ahead:
        curr2 = curr2.next;
    }
    return true;
}

谢谢！

标签： javascriptlinked-listsingly-linked-listpalindrome

解决方案

在第一个 while 循环中，您正在推动l.value但l没有递增，因此它将相同的值推送到arr。

你现在有arr，它应该是l反向的。在第二个 while 循环中，而不是使用arr.shift()使用arr.pop()。这将从arr堆栈中取出第一个元素。请记住，堆栈是先进后出的。

另请注意，当您从前到后比较列表时，您将到达一个不相关的点，即中间点。一旦您知道正向列表中的一半值与反向列表中的值相同，您就知道其余的将通过测试。

这就是它的样子。你应该试着弄清楚如何自己做赔率。

function isListPalindrome(l) {
  let curr = l;
  let arr = [];

  if (l == null)
      return true;

  // push all elements of l into the stack.
  // a stack in JS is an array.
  while(curr != null){
    arr.push(curr.value);

    // move ahead:
    curr = curr.next;
  }

  let curr2 = l;
  let length = arr.length;
  // Traverse the list again & check by popping from the stack:
  while(curr2 != null){

    // get the top most element on the stack:
    let lastNum = arr.pop();

    // check if the node data isn't the same as the element popped:
    if (curr2.value != lastNum){
      return false;
    }

    // Half way point for evens
    if (length / 2 === arr.length) {
      return true;
    }

    // move ahead:
    curr2 = curr2.next;
  }
  return true;
}

推荐阅读