リンクされたリストを最小値の周りに分割する方法

Question

再帰を使用してリンクリストの選択ソートを実行しようとしていますが、再帰的ソート機能を通過するたびに最小値を持つノードのリンクリストを分割する際に問題があります。 。最小の値を持つノードを取得しようとしています。リンクされたリストを最小値の周りに分割し、最小のものを前面に追加し、2つの分割リストを結合し、連結リスト全体がソートされるまで、ソートされます。たとえば、

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

は私のアペンドであり、メソッドへの参加：

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ではない方法で変数の種類として何回か使用します。変数はブロック（ブロックスコープ変数の場合はECMAScript6 let）で宣言します。 this questionを見てください。だから、たとえば最小にあなたが書いた：sortで

var sm = next.smallest(); 

を使用すると、2つの追加的な問題を抱えている：まず、あなたは関数がそれらを交換しますオブジェクトを割り当てますことを期待してパラメータとしてnull変数を渡す（に関する説明hereを見ますJSにおける参照値変数の性質（プリミティブ値ではない）。第二に、あなたは、私はsmallestが（splitItが正常に動作している場合）で、このリンクリストに追加されてますが、無限ループを持っていると思う忘れてしまったが、appendSmallest

に

else { next.appendSmallest(smallest);} 

このラインを持っている意味と仮定すると同じです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; 
    } 
}