Interesting JavaScript question: Merge sort of linked list-JS Tutorial-php.cn

Interesting JavaScript question: Merge sort of linked list

黄舟

Release： 2017-01-22 15:04:13

Original

1867 people have browsed it

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

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

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 (www.php.cn)!