Skip to content

Instantly share code, notes, and snippets.

@vampaynani
Created August 1, 2019 20:50
Show Gist options
  • Save vampaynani/fd7a958934d297459e781e5de9428b9a to your computer and use it in GitHub Desktop.
Save vampaynani/fd7a958934d297459e781e5de9428b9a to your computer and use it in GitHub Desktop.
How to apply merge sort on a single linked list
class Node{
constructor(value){
this.value = value;
this.next = null;
}
}
class LinkedList{
constructor(value){
this.head = value ? new Node(value): null;
}
insertLast(value){
if(!value) return;
let last = this.head;
if(!last){
this.head = new Node(value);
}
while(last.next !== null){
last = last.next;
}
last.next = new Node(value);
}
}
const ll = new LinkedList(1);
ll.insertLast(5);
ll.insertLast(3);
ll.insertLast(2);
ll.insertLast(6);
mergeSort(ll.head);
console.log(JSON.stringify(ll));
function getMiddle(node){
if(!node){
return node;
}
let fastPtr = node.next;
let slowPtr = node;
while(fastPtr !== null){
fastPtr = fastPtr.next;
if(fastPtr !== null){
slowPtr = slowPtr.next;
fastPtr = fastPtr.next;
}
}
return slowPtr;
}
function mergeSort(head){
if(!head || !head.next){
return head;
}
const middle = getMiddle(head);
const middleRight = middle.next;
middle.next = null;
const left = mergeSort(head);
const right = mergeSort(middleRight);
console.log('left',JSON.stringify(left));
console.log('right',JSON.stringify(right));
return sort(left, right);
}
function sort(left, right){
let result;
if(!left) return right;
if(!right) return left;
if(left.value <= right.value){
result = left;
result.next = sort(left.next, right);
}else{
result = right;
result.next = sort(left, right.next);
}
return result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment