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;  
}

以上就是JavaScript趣題：鍊錶的歸併排序的內容，更多相關內容請關注PHP中文網（www.php.cn）！