partitioning a linkedlist in javascript

Question

I am trying to partition a linkedlist but can't seem to get it to work when there are no elements less than the current value that you are looking at. the idea is based on the val, items less than the parameter value go to the left in the linkedlist and items greater than the parameter value go to the right. I changed some of the conditions for adding to the "greaterThan" and "lessThan" linkedlists, but then it would stop working if the item was in the middle. What am i missing? Have been stuck on this for quite a bit. the most relevant function here is the "partition" function, everything else is a helper.

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

Tests:

    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/

Testing your fiddle, I can't find anything wrong with it. Are you able to include an example of expected output, and console output? — Matt Way
– Matt Way, Commented Nov 15, 2015 at 3:16
Yes, I provided that at the bottom of the JS fiddle, see the comments: jsfiddle.net/e76vcwtp/1 — devdropper87
– devdropper87, Commented Nov 15, 2015 at 3:18
All of the provided examples are correct. I'm still not sure what your problem is. — Matt Way
– Matt Way, Commented Nov 15, 2015 at 3:19
The 2nd and 4th examples aren't correct. in the 2nd example 4 should be at the very beginning since you are partitioning, everything greater than it goes to the right — devdropper87
– devdropper87, Commented Nov 15, 2015 at 3:21

Matt Way · Accepted Answer · 2015-11-15 03:25:15Z

2

The results you are getting are correct in terms of the code you have written, however to get the ordering you want you simply need to move the = sign to the less than side.

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

answered Nov 15, 2015 at 3:25

Matt Way

33.3k10 gold badges85 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Matt Way Over a year ago

The result of the first is exactly the same 8459, and the result of the second is now 4859, which is exactly what you asked for in chat. I have flagged the question, and suggest you rewrite it to be more clear about what it is that you want vs get.

devdropper87 Over a year ago

yes, you're right about the second one, my fault. so it's only the first one, which returns 8459, but should return 4589 or even 5489

devdropper87 Over a year ago

I think i was pretty clear in my description. "items less than go to the left and greater than to the right." linkedlist.partition(8) cannot return "8459", which I explained in the description. i also mentioned that I tried what you suggested and it did not work, which is still the case after you suggested what I tried. items less than 8 need to go to the left. nonetheless, I'll make it clearer.

Radio- · Accepted Answer · 2015-11-15 03:36:09Z

You don't really handle the partition point very well when partitioning or merging the lists. a) you iterate over it when partitioning b) you don't handle it when merging the lists back together

It also begs the question of what's supposed to happen if you choose a partition point that's not in the list.

One way to handle what you have now without regard to points not in the list is to start greaterThanVal with your partition point, don't consider your partition point during partitioning, and then merge the two lists as long as lesserThanVal is not 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;
  }
}

Collectives™ on Stack Overflow

partitioning a linkedlist in javascript

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related