Strategien zur Umkehrung einer verknüpften Liste in JavaScript

Ich gerade kämpfte sich durch eine einfache interview-Frage: Bitte Rückseite eine einfach verknüpfte Liste.

Während ich versäumt, eine Arbeit in der Zeit zu beantworten, um speichern Sie das interview, ich war in der Lage zu kommen mit einer Lösung danach.

Ist meine Lösung korrekt? Wie würden Sie analysieren diese mit der Big-Oh? Gibt es noch effizientere Möglichkeiten für das reverse eine einfach verknüpfte Liste?

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

Hinweis: auf meiner Suche nach ähnlichen Beiträgen, das habe ich ein Beispiel in JavaScript. Ich Frage mich, ob mein code ist möglich (ohne temp variable). Danke.

InformationsquelleAutor user2954463 | 2014-04-24

  1. 21

    Gibt es ein paar Probleme mit dem code. Dies sollte klar stellen.

    //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);
    Cheers!

    InformationsquelleAutor stark

  2. 4

    Wäre dies O(n) Zeit, da Sie eine Konstante Anzahl von Operationen auf jeden Knoten. Konzeptionell gibt es nicht einen effizienteren Weg, Dinge zu tun (in Bezug auf die groß-O-notation es gibt einige code-Optimierung getan werden könnte.)

    Den Grund, warum Sie können nicht mehr als O(n) ist da, um dies zu tun, müssen Sie überspringen einige Knoten. Da müssen Sie zum ändern jeder Knoten wäre dies nicht möglich.

    Effizienz kommt dann von unten auf einen Konstanten Faktor. Je weniger Operationen, die Sie tun können pro Eintrag in der Liste, desto schneller wird Ihr code ausgeführt wird.

    Ich würde umsetzen wie diese:

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

    Dies ist natürlich rekursiv, so wäre es ineffizient im Sinne von Raum, aber ich mag rekursiven code 🙂

    Diese auch nicht zurück die Umgekehrt verkettete Liste, aber wir konnten relativ leicht ändern, Dinge zu tun, also wenn das wichtig ist.

    Vielen Dank für Ihre Antwort und Ihre Analyse von Big-O, sehr geschätzt.

    InformationsquelleAutor ckersch

  3. 4

    Könnte man dieses problem lösen rekursiv in O(n) Zeit wie ckersch erwähnt. Die Sache ist, dass Sie brauchen, um zu wissen, dass Rekursion ist speicherintensiv, da Funktionen akkumulieren sich in den anrufen Stapel, bis Sie auf den stop-Zustand und starten die Rückkehr tatsächlichen Dinge.

    Die Möglichkeit, ich würde dieses problem zu lösen ist:

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

    Wenn reverse() erreicht das Ende der Liste, wird er schnappen Sie sich die letzten Knoten als neuer Leiter und Referenz für jeden Knoten rückwärts.

    InformationsquelleAutor Rantelo

Schreibe einen Kommentar