归并排序想必大家都知道，它的基本思想，是一个先分割，再合并的过程。
那么，如何对一条单链表进行归并排序呢？
首先，我们需要一个分割链表的方法，如下面的伪代码所展示的那样：
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
它接收一个链表的尾指针作为参数，将该链表一分为二，也就是前半部分和后半部分。
那么，这个中间的分界值该如何确定下来？
可以使用快慢指针，快指针和慢指针同时从尾部出发，遍历单链表，快指针每次都走2步，慢指针每次走1步，那么快指针肯定会先达到终点，而慢指针此时只走了一半的路程，也就是说，慢指针正好处于这个分界的位置。
那剩下的就好办了，在分界处截断，该设置为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;
}
然后，链表打散了，甚至成了一个个不可分割的单元节点，我们就要想办法将它们合并，组装成新的有序的链表，于是，就需要下面的merge方法：
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
要写好一个这样的方法，考虑的case其实是有蛮多的，这在俺的代码里就有所体现了：
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;
}
以上就是javascript趣题：链表的归并排序的内容。