[Solved] how to merge two sorted linked lists in python [closed]

by


This operation is just doing the “merge” step of a Merge Sort and can be done in O(l1+l2) time.

The general premise is to iterate over both (already sorted) lists at the same time, but only advance the list with the lowest head value, while using the advanced value in the resulting output. The operation is complete when both source lists are exhausted.

Here is some pseudo-code (courtesy of the Wikipedia) and shouldn’t be too hard to translate for a linked list data-type. When implementing it for a linked list a new list can either be created or one of the lists can be destructively modified.

function merge(left, right)
    // receive the left and right sublist as arguments.
    // 'result' variable for the merged result of two sublists.
    var list result
    // assign the element of the sublists to 'result' variable until there is no element to merge. 
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
           // compare the first two element, which is the small one, of each two sublists.
            if first(left) <= first(right)
                // the small element is copied to 'result' variable.
                // delete the copied one(a first element) in the sublist.
                append first(left) to result
                left = rest(left)
            else
                // same operation as the above(in the right sublist).
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            // copy all of remaining elements from the sublist to 'result' variable, 
            // when there is no more element to compare with.
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            // same operation as the above(in the right sublist).
            append first(right) to result
            right = rest(right)
    end while
    // return the result of the merged sublists(or completed one, finally).
    // the length of the left and right sublists will grow bigger and bigger, after the next call of this function.
    return result

7

solved how to merge two sorted linked lists in python [closed]