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

它接收一个链表的尾指针作为参数，将该链表一分为二，也就是前半部分和后半部分。

那么，这个中间的分界值该如何确定下来？

可以使用快慢指针，快指针和慢指针同时从尾部出发，遍历单链表，快指针每次都走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; 
}