Стратегии для изменения связанного списка в JavaScript

Я просто попытался решить простой вопрос: пожалуйста, отмените список, связанный с одинокой.

В то время как я не смог предоставить рабочий ответ вовремя, чтобы сохранить интервью, после этого мне удалось найти решение.

Правильно ли мое решение? Как бы вы проанализировали это с помощью Big-Oh? Есть ли более эффективные способы обращения к одному связанному списку?

// reverse a linked list

var reverseLinkedList = function(linkedlist) {
  var node = linkedlist;
  var previous = null;

  while(node) {
    // reverse pointer
    node.next = previous;
    // increment previous to current node
    previous = node;
    // increment node to next node
    if (node.next){
      node = node.next
    } else {
      node = null;
    }
  }
}

Примечание. В моем поиске похожих сообщений я нашел один пример в JavaScript. Мне было интересно, возможен ли мой код (без переменной temp). Спасибо.

Ответ 1

Есть пара проблем с вашим кодом. Это должно дать понять.

// reverse a linked list  
var reverseLinkedList = function(linkedlist) {
  var node = linkedlist;
  var previous = null;

  while(node) {
    // save next or you lose it!!!
    var save = node.next;
    // reverse pointer
    node.next = previous;
    // increment previous to current node
    previous = node;
    // increment node to next node or null at end of list
    node = save;
  }
  return previous;   // Change the list head !!!
}
linkedlist = reverseLinkedList(linkedlist);

Ответ 2

Вы можете решить эту проблему рекурсивно в O (n) раз, как упоминается ckersch. Дело в том, что вам нужно знать, что рекурсия является интенсивной в памяти, поскольку функции накапливаются в стекх вызовов до тех пор, пока они не достигнут состояния остановки и не начнут возвращать реальные вещи.

Как я решил эту проблему:

 const reverse = (head) => {
   if (!head || !head.next) {
     return head;
   }
   let temp = reverse(head.next);
   head.next.next = head;
   head.next = undefined;
   return temp;
 }

Когда reverse() достигнет конца списка, он возьмет последний node в качестве новой главы и ссылается на каждый node назад.

Ответ 3

Это будет O (n) во времени, так как вы выполняете постоянное количество операций на каждом node. Понятно, что нет более эффективного способа делать вещи (с точки зрения обозначения O-O, существует некоторая оптимизация кода, которая может быть выполнена.)

Причина, по которой вы не можете превышать O (n), заключается в том, что для этого вам нужно будет пропустить некоторые узлы. Поскольку вам нужно изменить каждый node, это было бы невозможно.

Эффективность затем сводится к постоянному коэффициенту. Чем меньше операций вы можете сделать для каждого элемента в списке, тем быстрее будет выполняться ваш код.

Я бы выполнил следующее:

function reverseLinkedList(list, previous){

  //We need to use the the current setting of
  //list.next before we change it. We could save it in a temp variable,
  //or, we could call reverseLinkedList recursively
  if(list.next !== null){
    reverseLinkedList(list.next, list);
  }

  //Everything after 'list' is now reversed, so we don't need list.next anymore.
  //We passed previous in as an argument, so we can go ahead and set next to that.
  list.next = previous;
}

reverseLinkedList(list, null);

Конечно, это рекурсивно, поэтому было бы неэффективно с точки зрения пространства, но мне нравится рекурсивный код:)

Это также не возвращает обратный связанный список, но мы могли бы довольно легко изменить его, если бы это было важно.