Strateji

Question

Bağlantılı bir liste tersine çevirmek için stratejiler Sadece basit bir röportaj soru ile mücadele etti: Lütfen tek başına bağlı bir listeyi ters çevirin. Röportajı kaydetmek için zamanında çalışan bir cevap veremediğim halde, daha sonra bir çözüm bulabildim.

Çözümüm doğru mu? Bunu Big-Oh ile nasıl analiz ederdiniz? Tek tek bağlı bir listeyi tersine çevirmenin daha etkili yolları var mı?

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

Not: Benzer mesajlar için zaman ara, ben JavaScript one example buldunuz. Benim kodumun (temp değişken olmadan) mümkün olup olmadığını merak ediyordum. Teşekkür ederim.

Answer 1

Kodunuzda birkaç sorun var. Bu açık olmalı.

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

Answer 2

Her düğümde sabit sayıda işlem yaptığınızdan, zaman içinde O (n) olur. Kavramsal olarak, bir şey yapmanın daha etkili bir yolu yoktur (büyük-O notasyonu açısından, yapılabilecek bazı kod optimizasyonu vardır.)

O (n) değerini alamamanın nedeni şu şekildedir: Bunu yapmak için bazı düğümleri atlamanız gerekir. Her bir düğümü değiştirmeniz gerektiğinden, bu mümkün olmazdı. Verimlilik daha sonra sabit bir faktöre iner. Listede öğe başına yapabileceğiniz daha az işlem, kodunuzun daha hızlı çalışmasını sağlar.

Böyle uygulamak istiyorum:

Tabii

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

, bu alan bakımından verimsiz olurdu böylece bu, özyinelemeli, ama özyinelemeli kod :)

Bu aynı zamanda kötü kokan gibi Tersine çevrilmiş bağlantılı listeyi döndür, ancak eğer önemliyse, bunu yapmak için işleri kolayca değiştirebiliriz.

Answer 3

Bu sorunu yinelemeli olarak O (n) saatte ckersch söz konusu olduğunda çözebilirsiniz. Mesele şu ki, yinelemenin bellek yoğun olduğu bilinmelidir, çünkü işlevler çağrı yığında durma durumuna gelene ve gerçek şeylere dönene kadar birikecektir. Bu sorunu çözmek olur

yöntemdir:

ters() listenin sonuna

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

, yeni kafanın geçen düğümü kapmak ve geriye doğru her bir düğümde referans alır.