-
Notifications
You must be signed in to change notification settings - Fork 0
/
mergeSortLinkedList.js
68 lines (64 loc) · 1.22 KB
/
mergeSortLinkedList.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
function linkedList(){
this.head = null;
this.tail = null;
this.length = function(){
var count = 0;
var current = this.head
while(current){
count++;
current = current.next;
}
return count;
}
this.add = function(value){
if(!this.head){
this.head = new node(value);
this.tail = this.head;
} else {
current = this.head;
while(current.next){
current = current.next
}
current.next = new node(value);
this.tail = current.next;
}
}
this.removeHead = function(){
originalHead = this.head;
if(this.head.next){
this.head = this.head.next
} else {
this.head = null;
}
return originalHead;
}
}
function node(value){
this.value = value;
this.next = null;
}
function mergeSortList(list){
var length = list.length();
var left = new linkedList;
var right = new linkedList;
if(list.length < 2){
return list;
}
for(var i = 0; i < length; i++){
if(i < length / 2){
left.add(list.removeHead());
} else {
right.add(list.removeHead());
}
}
return merge(mergeSortList(left), mergeSortList(right));
}
function merge(left, right){
var output = new linkedList();
}
var list = new linkedList();
list.add(5);
list.add(10);
list.add(11);
list.removeHead();
console.log(list);