Проверьте, является ли связанный список палиндромом в JavaScript - PullRequest
Новая
       8

Проверьте, является ли связанный список палиндромом в JavaScript

0 голосов
/ 07 января 2020

Я написал следующую функцию в JavaScript, чтобы проверить, является ли односвязный список палиндромом. Однако я проваливаю 2 из 10 тестов и не могу понять, почему.

Вот тесты, которые я проваливаю.

  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;
}

Спасибо!

1 Ответ

1 голос
/ 07 января 2020

Внутри первого, пока l oop вы нажимаете l.value , но l не увеличивается, поэтому оно возвращает то же значение в arr .

Теперь у вас есть обр , который, как предполагается, равен l в обратном порядке. Во втором, пока l oop, вместо использования 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;
}
...