0

hello fellow programmers, i am doing an assignment for class and i am having a bit of trouble. So the assignments reads Given two sorted (in ascending order) lists of size M and N, write an O(M+N) algorithm to find the sorted (also in ascending order) union of the two lists. Assume each list contains no duplicate items.

I know that i want to use a MergeSort to merge the two lists together, i just dont know how to write in code. So far i have:

template<typename T>
list<T> listUnion(const list<T>& one, const list<T>& two) {
    list<T> result;

    std::list<T>::iterator modifIter;
    modifIter = two.begin();
    while(modifIter != one.end())
    {
        result.push_back(two);
        ++modifIter;
    }

    result.merge(one);

    return result;
}

i am trying to use an iterator to iterate through the 2nd list. and the while loop is for while the beginning of the 2nd list is not at the end of the 1st i want to add the 2nd lists' elements to a third list, result. then increment the iterator to the next element in the 2nd list. after that is done i merge the third list (result) and the 1st list (one), then return the third list. Does this code work or no? I'd appreciate any advice!!!

2
Contributors
3
Replies
14
Views
3 Years
Discussion Span
Last Post by tinstaafl
1

Looks to me like you'll acheive the same result with

list<T> result = two;
return result.merge(one);

Which if I'm not mistaken is O(M+N-1), according to this reference

Edited by tinstaafl

0

To me it seems redundant. You're using an iterator to add two to result, instead of a straight assignment statement.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.