Interesting JavaScript question: Merge sort of linked list

Everyone must know that merge sorting is a process of first dividing and then merging.

So, how to merge sort a singly linked list?

First, we need a method to split the linked list, as shown in the following pseudocode:

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

It receives the tail pointer of a linked list as a parameter and divides the linked list into two , that is, the first half and the second half.

So, how to determine this intermediate dividing value?

You can use fast and slow pointers. The fast pointer and the slow pointer start from the tail at the same time and traverse the singly linked list. The fast pointer takes 2 steps each time and the slow pointer takes 1 step each time. Then the fast pointer will definitely reach the end first. , and the slow pointer has only traveled half the distance at this time, that is to say, the slow pointer is exactly at this dividing position.

The rest is easy to handle. Truncate at the boundary and set the setting to null. We have completed the first stage.

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

Then, the linked list is broken up and even becomes indivisible unit nodes. We have to find a way to merge them and assemble them into a new ordered linked list. Therefore, we need the following merge Method:

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

To write such a method, there are actually quite a lot of cases to consider, which is reflected in my code:

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

Okay, split The methods and merging methods are all written down, just like the chopping board and kitchen knife are ready, all you need to do is cut the meat. Main method This is a recursive process.

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

The above is an interesting JavaScript question: the content of merge sorting of linked lists. For more related content, please pay attention to the PHP Chinese website (m.sbmmt.com)!