So I was trying to basically sort and merge two linked list using Mergesort
.
So, this is the code that creates and iterates a linkedlist in JavaScript
which I guess is working fine.
function Node(data) {
this._data = data;
this.next = null;
}
function LinkedList(_listHead) {
this.head = _listHead || null;
}
LinkedList.prototype.insert = function(val) {
var head = this.head;
if(head === null) {
this.head = new Node(val);
}else {
var currentNode = head;
while(currentNode.next !== null) {
currentNode = currentNode.next;
}
currentNode.next = new Node(val);
}
}
LinkedList.prototype.iterate = function() {
var head = this.head;
if(head === null) {
return null;
}else {
var currentNode = head;
while(currentNode !== null) {
console.log(currentNode._data);
currentNode = currentNode.next;
}
}
}
But my merge sort
algo is not working. What am I doing wrong?
LinkedList.prototype.mergeSort = function() {
var count = 0;
if(this.head === null) {
return null;
}
else if(this.head.next === null) {
return this.head;
}
var currentNode = this.head;
while(currentNode !== null) {
count++;
currentNode = currentNode.next;
}
var mid = Math.floor(count/2);
var count2 = 0;
var rightPointer = this.head;
while(count2 < mid) {
rightPointer = rightPointer.next;
count2++;
}
// Assign both the halves
var rightList = new LinkedList(rightPointer.next);
var leftList = new LinkedList(null);
return new merge(this.mergeSort(leftList),this.mergeSort(rightList));
}
LinkedList.prototype.merge = function(leftList,rightList) {
var resultList = new LinkedList();
var resultPointer = resultList.head;
var leftPointer = leftList.head;
var rightPointer = rightList.head;
while(leftPointer !== null && rightPointer !== null) {
var tempNode = null;
if(leftPointer._data < rightPointer._data) {
tempNode = leftPointer._data;
leftPointer = leftPointer.next;
}else {
tempNode = rightPointer._data;
rightPointer = resultPointer.next;
}
if(resultList.head === null) {
resultList.head = new Node(tempNode);
resultPointer = resultList.head;
}else {
resultPointer.next = new Node(tempNode);
resultPointer = resultPointer.next;
}
}
// Iterate the rest of the lists
if(leftPointer.next === null) {
while(rightPointer !== null) {
resultPointer.next = rightPointer.next;
resultPointer = resultPointer.next;
}
}else {
while(leftPointer !== null) {
resultPointer.next = leftPointer.next;
resultPointer = resultPointer.next;
}
}
return resultList.head;
}
Please explain.
Comments
Post a Comment