Удалить узлы из связанного списка на основе значения - PullRequest
Новая
       44

Удалить узлы из связанного списка на основе значения

0 голосов
/ 12 октября 2018

Я работаю над проблемой Hackerrank и пытаюсь удалить все узлы, которые превышают определенное значение.

Это их базовая реализация 

const SinglyLinkedListNode = class{
  constructor(value) {
    this.value = value;
    this.next = null;
  }
};

const SinglyLinkedList = class {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  insertNode(value) {
    const node = new SinglyLinkedListNode(value);
    if(!this.head) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
  }
};

Моя функция для удаления узловимеет следующий вид ... 

SinglyLinkedList.prototype.removeNodes = function(listHead, x){
  let currentNode = listHead;

  while(currentNode !== null && currentNode.next !== null) {
    let next = currentNode.next;
    while (next !== null && next.value > x) {
      next = next.next
    }
    currentNode.next = next
    if(currentNode.next === null) {
      break;
    }
  }
  return currentNode
}

Параметры: listhead - ссылка на корневой узел и x - целочисленное значение для фильтрации связанного списка

Так, например, LLis 1-> 2 -> 4 -> 3 -> 5, и мне нужно удалить все узлы, больше чем x (3) и поддерживать целостность порядка LL.Результат должен быть 1 -> 2 -> 3.

Я не понимаю, почему я продолжаю получать this.tail.value = 5 вместо this.tail.value = 3, this.tail.next =null.

это REPL

1 Ответ

0 голосов
/ 12 октября 2018

Потому что tail необходимо явно переписать, так как в противном случае он сохраняет ссылку на несвязанный узел.Перед запуском функции список выглядит следующим образом: 

  list: head                                   tail
           1    ->    2   ->    3  ->    4    ->  5

, а затем хвост все еще указывает на 5, хотя это не связано: 

 list: head                                  tail
         1    ->    2   ->    3             5

Чтобы решить эту проблему, просто перепишите хвост вконец вашей функции: 

 return this.tail = currentNode;

Кроме того, вы фактически должны просмотреть список, поэтому добавьте 

 currentNode = currentNode.next;

в конец внешнего while.

...