用javascript对链表进行分区

Question

我正在尝试对linkedlist进行分区，但当没有小于当前值的元素时，似乎无法使其工作。这个想法是基于val的，小于参数值的项目在linkedlist中向左，大于参数值的项向右。我更改了添加到"greaterThan"one_answers"lessThan"链接列表的一些条件，但如果该项目位于在中间，它将停止工作。我错过了什么？我在这个问题上已经坚持了很长一段时间。这里最相关的函数是"partition"函数，其他的都是辅助函数。

var LinkedList = function () {
  this.head = null;
  this.tail = null;
};
LinkedList.prototype.makeNode = function (val) {
  var node = {};
  node.val = val;
  node.next = null;
  return node;
};
LinkedList.prototype.partition = function (val) {
  var lesserThanVal = new LinkedList();
  var greaterThanVal = new LinkedList();
  var iterator = this.head;
  while (iterator) {
    if (iterator.val < val) {
      lesserThanVal.addToTail(iterator.val);
    } else if (iterator.val >= val) {
      greaterThanVal.addToTail(iterator.val);
    }
    iterator = iterator.next;
  }
  //now merge them.
  if (lesserThanVal.head === null) {
    console.log("LESSER IS NULL")
    return greaterThanVal;
  }
  if (greaterThanVal.head === null) {
    console.log("GREATER IS NULL")
    return lesserThanVal;
  } else {
    //merge
    var pointer = lesserThanVal.head;
    while (pointer.next) {
      pointer = pointer.next;
    }
    pointer.next = greaterThanVal.head;
    lesserThanVal.tail = greaterThanVal.tail;

    console.log("SHOULD BE 9", lesserThanVal.head.next.next);
    return lesserThanVal;
  }
};
LinkedList.prototype.addToTail = function (value) {
  var newTail = this.makeNode(value);
  if (!this.head) {
    this.head = newTail;
  }
  if (this.tail) {
    this.tail.next = newTail;
  }
  this.tail = newTail;
};

---

测试：

    var list = new LinkedList();
    list.addToTail(8);
    list.addToTail(4);
    list.addToTail(5);
    list.addToTail(9);


 console.log(list);
    var partitionedList = list.partition(8); 
    returns { head: { val: 4, next: { val: 5, next: [8...] } },
      tail: { val: 9, next: null } }
    var partitionedList = list.partition(4); 
    returns { head: { val: 8, next: { val: 4, next: [5...] } },
      tail: { val: 9, next: null } }
    var partitionedList = list.partition(9); 
    returns { head: { val: 8, next: { val: 4, next: [{5...}] } },
      tail: { val: 9, next: null } }
    var partitionedList = list.partition(5);
    returns { head: { val: 4, next: { val: 8, next: [{5....}] } },
      tail: { val: 9, next: null } }
    console.log(partitionedList);

小提琴：https://jsfiddle.net/e76vcwtp/

Answer 1

根据您编写的代码，您得到的结果是正确的，但是要获得所需的排序，只需将=符号移到小于一侧即可。

while(iterator){
    if(iterator.val <= val){
        lesserThanVal.addToTail(iterator.val);
    }else if(iterator.val > val){
        greaterThanVal.addToTail(iterator.val);
    }
    iterator = iterator.next;
}

Answer 2

在对列表进行分区或合并时，您并不能很好地处理分区点。a） 分区时对其进行迭代b） 当将列表重新合并在一起时，您无法处理它

这也引出了一个问题，如果你选择了一个不在列表中的分区点，会发生什么。

在不考虑不在列表中的点的情况下处理现在所拥有的内容的一种方法是用您的分区点启动greaterThanVal，在分区过程中不要考虑您的分区，然后只要lesserThanVal不为null，就合并两个列表。

greaterThanVal.addToTail(val);
while (iterator) {
    if (iterator.val < val) {
      lesserThanVal.addToTail(iterator.val);
    } else if (iterator.val > val) {
      greaterThanVal.addToTail(iterator.val);
    }
    iterator = iterator.next;
  }
  //now merge them.
  if (lesserThanVal.head === null) {   
    return greaterThanVal;
  } else {
    var pointer = lesserThanVal.tail;
    pointer.next = greaterThanVal.head;
    lesserThanVal.tail = greaterThanVal.tail;
    return lesserThanVal;
  }
}