在 javascript 中划分链表

Question

我正在尝试对链表进行分区，但是当没有小于您正在查看的当前值的元素时，它似乎无法工作。这个想法是基于val，小于参数值的项目在链表中向左移动，大于参数值的项目向右移动。我更改了一些添加到 "greaterThan" 和 "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);

fiddle: 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不为空。

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

在 javascript 中划分链表

partitioning a linkedlist in javascript

javascript

algorithm

linked-list

data-structures