JavaScript趣题:链表的归并排序
程序员文章站
2022-04-04 08:02:41
...
归并排序想必大家都知道,它的基本思想,是一个先分割,再合并的过程。
那么,如何对一条单链表进行归并排序呢?
首先,我们需要一个分割链表的方法,如下面的伪代码所展示的那样:
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趣题:链表的归并排序的内容,更多相关内容请关注PHP中文网(www.php.cn)!