Как связать связанный список с минимальным значением

Question

Я пытаюсь выполнить сортировку сортировки в связанном списке, используя рекурсию, и у меня возникли проблемы с разбиением связанного списка вокруг узла с наименьшим значением на каждом проходе через мою рекурсивную функцию сортировки , Я пытаюсь получить узел с наименьшим значением, разделяю связанный список по наименьшему значению, добавляю наименьшее на передний план, присоединяюсь к двум секционированным спискам и затем снова выполняю сортировку в объединенном секционированном списке до тех пор, пока весь связанный список сортируется. Например:

q w e r t // partition around e 
e -> q w r t // join the partitions 
eq -> w r t // append q to e 
eq -> w r t // partition around r 

и пр.

Мой метод сортировки:

Node.prototype.sort = function(){ 
    if(!next){ 
     return this; 
} else { 
    var a = null; 
    var b = null; 
    var smallest = this.smallest(); 
    splitIt(smallest, a, b); 
    appendSmallest(smallest); 
    a.join(b); 
    a.sort(); 
    } 
} 

я получаю самый маленький узел так:

Node.prototype.smallest = function(){ 
    if(!next) return this; 
    var sm = next.smallest(); 
    if(sm.data < this.data){ 
     return sm; 
    } 
    return this; 
} 

Вот мой Append и методы соединения:

Node.prototype.appendSmallest = function(smallest){ 
    if(!next) next = smallest; 
} 


Node.prototype.join = function(otherNode){ 
    if(!next) next = otherNode; 
    else next.join(otherNode); 
} 

У меня возникли некоторые проблемы реализуя метод splitIt рекурсивно. Что такое псевдокод для такой операции?

Answer 1

Я предполагаю, что вы используете чистый JavaScript, так как нет никакого указания.

В вашем коде вы используете несколько раз слово Node как тип переменной типа, который недопустим JS. Вы объявляете переменные со словом var (и в ECMAScript6 let для переменных с охватом блоков). Посмотрите на this question. Так, например, в Наименьший Вы пишете:

var sm = next.smallest(); 

В sort у вас есть две дополнительные проблемы: во-первых, вы передаете нулевые переменные в качестве параметров в надежде, что функция будет присваивать объекты, которые заменят их (см объяснение here относительно характер ссылочных переменных (не примитивно оцененных) в JS). Во-вторых, предполагая, что вы забыли, но имел в виду, чтобы иметь эту линию в appendSmallest

else { next.appendSmallest(smallest);} 

, то я думаю, что у вас есть бесконечный цикл, поскольку smallest прилагается к настоящему связного списка, который (если splitIt работает должным образом) так же, как a.

Мое предложение делает раскол и объединить вместе, как функции «spitSmallest»:

Node.prototype.spitSmallest = function(smallest){ 
    //we know that this node is not smallest 
    if (this.next == smallest){ 
     this.next = this.next.next; 
     smallest.next = null; //again not really needed 
    } else { 
     this.next.spitSmallest(smallest); 
    } 
} 

Node.prototype.sort = function(){ 
    if(!this.next){ 
     return this; 
} else { 
    var smallest = this.smallest(); 
    var restHead; 
    if (smallest==this){ 
     restHead = this.next; 
     this.next = null; //not needed but makes it more readable 
    } else { 
     restHead = this; 
     this.spitSmallest(smallest); 
    } 
    smallest.next = restHead.sort(); 
    return smallest; 
    } 
}