javascript - 如何围绕最小值划分链表

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

这是我的附加和连接方法:

 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 用于 block 范围变量)。看this question .因此，例如在最小的你写:

var sm = next.smallest();

在 sort 中你有两个额外的问题:首先，你将 null 变量作为参数传递，希望函数分配将替换它们的对象(参见关于引用性质的解释 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;
  }
}