LaVOZs

The World’s Largest Online Community for Developers

'; algorithm - Merge sort with insertion function - LavOzs.Com

I have two sorted linked list l1 and l2. I wanted to merge l2 into l1 while keeping l1 sorted. My return statement is l1 sorted and l2 is an empty list. How do I approach this problem by using insert_before, insert_after, and remove_node function? Any ideas?

If you know how linked lists are implemented, you can easily just iterate through both of them, using something like the approach below. If you don't know too much about linked lists you might want to read up on those first.

if(l1 == null || l2 == null){
    return l1==null ? l2 : l1;
indexA = indexB = 0;
elemA = l1.get(0);
elemB = l2.get(0);
while(indexA<l1.size() || indexB<l2.size()){   
    if(indexA==l1.size()){
        l1.insert_after(l1.size()-1,elemB);
        indexA++;
        indexB++;
        if(indexB<l2.size()){
            elemB = l2.get(indexB);
        }
        continue;
    }
    if(indexB==l2.size()){
        break;
    }
    if(elemA<elemB){
        indexA++;
        if(indexA<l1.size()){
            elemA = l1.get(indexA);
        }
        continue;
    }
    if(elemA>elemB){
        l1.insert_before(indexA,elemB);
        indexA++;
        indexB++;
        if(indexB<l2.size()){
            elemB = l2.get(indexB);
        }
}
return l1;

this is a somehow java like implementation, it iterates through both lists and merges them together on the go. I decided to only return l1 as the empty list would be somewhat useless right?, all the inefficient get() calls could be avoided by writing an own simple LinkedList class to gain access to the next and last fields, which would greatly facilitate navigation.

If you could provide additional information about the methods you have available or the language this has to be written in I could probably provide you with better explanations.

Edit: Explanation


first both elemA /elemB are given the value of the first element in the linked lists then the while loop is used to iterate through them until the index values that are used to keep track of where we are in the lists are both too high (e.g. ==size of list)

Now the first two if statements are to check wheter one of the lists is already completely iterated through, if this is the case for the first list, the next element of the second list is just added behind the last element of l1, as it must be greater than it, otherwise indexA would not have been increased. (In this if statement indexA is also incremented because the size of the list is getting bigger and indexA is compared to l1.size() ), finally the continue statement skips to the next iteration of the loop.
The second if statement in the while loop tests if the second list has already completely been iterated through, if this is true there is nothing more to merge so the loop is stopped by the break statement.

below that is more or less classic mergesort;
if the current element of l1 is smaller than the current element of l2, just go to the next element of l1 and go to next iteration of loop, otherwise insert the current element of l2 before elemA and iterate further here indexA is also incremented because otherwise it would not point to the right element anymore as an element was inserted before it.
is this sufficient?

Edit: Added testing if either of the lists is null as suggested by @itwasntme

The functions insert_before, insert_after, and remove_node are not clearly defined in the question. So assuming one of the parameters is a reference to the "list", is the other parameter an index, an iterator, or a pointer to a node? If the lists are doubly linked lists, then it makes sense for the second parameter to be an iterator or a pointer to a node (each node has a pointer to previous node, so there's no need to scan according to an index to find the prior node).

In the case of Visual Studio's std::list::sort, it uses iterators and std::list::splice to move nodes within a list, using iterators to track the beginning and ending of sub-lists during a merge sort. The version of std::list::splice used by std::list::sort combines remove_node and insert_before into a single function.

Related
How do I merge two dictionaries in a single expression?
How do I sort a list of dictionaries by a value of the dictionary?
How to merge a specific commit in Git
How to join (merge) data frames (inner, outer, left, right)
How do you merge two Git repositories?
How to merge two arrays in JavaScript and de-duplicate items
How to sort in-place using the merge sort algorithm?
How to detect a loop in a linked list?
Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
How to undo a git merge with conflicts