JavaScript趣题：链表的归并排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了JavaScript趣题：链表的归并排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2688字，纯文字阅读大概需要4分钟。

内容图文

那么，如何对一条单链表进行归并排序呢？

首先，我们需要一个分割链表的方法，如下面的伪代码所展示的那样：

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.gxlcms.com）！

内容总结

以上是互联网集市为您收集整理的JavaScript趣题：链表的归并排序全部内容，希望文章能够帮你解决JavaScript趣题：链表的归并排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端