JavaScript趣題：鏈表的歸并排序

var source = 1 -> 3 -> 7 -> 8 -> 11 -> 12 -> 14 -> null 
var front = new Node() 
var back = new Node() 
frontBackSplit(source, front, back) 
front === 1 -> 3 -> 7 -> 8 -> null 
back === 11 -> 12 -> 14 -> null

function Node(data) { 
 this.data = data === undefined ? null : data; 
 this.next = null; 
} 
 
function frontBackSplit(source, front, back) { 
 var total = 0; 
 var fast = source; 
 var slow = source; 
 var partial = null; 
 while(fast && fast.next){ 
 fast = fast.next.next; 
 slow = slow.next; 
 total++; 
 } 
 partial = slow; 
 while(slow){ 
 slow = slow.next; 
 total++; 
 } 
 if(total % 2 === 1){ 
 back.data = partial.next.data; 
 back.next = partial.next.next; 
 partial.next = null; 
 } 
 else{ 
 back.data = partial.data; 
 back.next = partial.next; 
 for(var e=source;e.next!=partial;e=e.next); 
 e.next = null; 
 } 
 front.data = source.data; 
 front.next = source.next; 
}

var first = 2 -> 4 -> 6 -> 7 -> null 
var second = 1 -> 3 -> 5 -> 6 -> 8 -> null 
sortedMerge(first, second) === 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 6 -> 7 -> 8 -> null

function sortedMerge(l1, l2) { 
 var newList = null; 
 var temp = null; 
 while(l1 && l2){ 
 if(l1.data > l2.data){ 
 if(!newList){ 
 newList = l2; 
 temp = l2; 
 } 
 else{ 
 temp.next = l2; 
 temp = l2; 
 } 
 l2 = l2.next; 
 } 
 else{ 
 if(!newList){ 
 newList = l1; 
 temp = l1; 
 } 
 else{ 
 temp.next = l1; 
 temp = l1; 
 } 
 l1 = l1.next; 
 } 
 } 
 if(l1){ 
 if(!newList){ 
 newList = l1; 
 } 
 else{ 
 temp.next = l1; 
 } 
 } 
 if(l2){ 
 if(!newList){ 
 newList = l2; 
 } 
 else{ 
 temp.next = l2; 
 } 
 } 
 return newList; 
}

function mergeSort(list) { 
 if(list && list.next){ 
 var front = new Node(); 
 var back = new Node(); 
 frontBackSplit(list, front, back); 
 return sortedMerge(mergeSort(front),mergeSort(back)); 
 } 
 return list; 
}