C++ merging two sorted lists(or arrays) with an O(M+N) algorithm

[TalentedIndividual]

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!!!

[tinstaafl]

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

[TalentedIndividual]

ok i agree..my question is does this code seem logical.?

[tinstaafl]

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