Merging Lists using iterators

Question

I need to merge two lists of strings in java and I'm not too sure on the best way to do it. I have to use iterators and the compareTo() method. For example...

Example: L1: A,B,C,D L2: B,D,F,G result: A,B,B,C,D,D,F,G

I can assume the input lists are already sorted and i cant use the contains() method. I have some initial checks but the while loop is what im stuck on.

public static ListADT<String> merge(ListADT<String> L1,ListADT<String> L2) throws BadListException {
ListADT<String> L3 = new ArrayList<String>;
if(L1 == null || L2 == null) {
    throw new BadListException();
}
Iterator<String> itr1 = new L1.iterator();
Iterator<String> itr2 = new L2.iterator();  
if(L1.size() == 0 && L2.size() == 0) {
    return L3;
}
if(L1.size() == 0 && L2.size() != 0) {
    for(int i = 0; i < L2.size(); i++) {
        return L3.add(L2.get(i));
    }
}
if(L2.size() == 0 && L1.size() != 0) {
    for(int i = 0; i < L1.size(); i++) {
        return L3.add(L1.get(i));
    }
}
while(itr1.hasNext() || irt2.hasNext()) {
    //merge the lists here?
}

}

Any help would be appreciated.

Answer 1

It's fairly straightforward if you just use variables to hold the current value from each iterator. This solution assumes your lists do not contain null, but it would not be difficult to add null-handling since the lists are sorted.

package com.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class IteratorMerge {

    /**
     * @param args
     */
    public static void main(String[] args) {
        List<String> list1 = Arrays.asList(new String[]{"A", "B", "C", "D"});
        List<String> list2 = Arrays.asList(new String[]{"B", "D", "F", "G"});

        System.out.println(merge(list1, list2));
    }

    public static List<String> merge(List<String> L1,List<String> L2) {
        List<String> L3 = new ArrayList<String>();

        Iterator<String> it1 = L1.iterator();
        Iterator<String> it2 = L2.iterator();

        String s1 = it1.hasNext() ? it1.next() : null;
        String s2 = it2.hasNext() ? it2.next() : null;
        while (s1 != null && s2 != null) {
            if (s1.compareTo(s2) < 0) { // s1 comes before s2
                L3.add(s1);
                s1 = it1.hasNext() ? it1.next() : null;
            }
            else { // s1 and s2 are equal, or s2 comes before s1
                L3.add(s2);
                s2 = it2.hasNext() ? it2.next() : null;
            }
        }

        // There is still at least one element from one of the lists which has not been added
        if (s1 != null) {
            L3.add(s1);
            while (it1.hasNext()) {
                L3.add(it1.next());
            }
        }
        else if (s2 != null) {
            L3.add(s2);
            while (it2.hasNext()) {
                L3.add(it2.next());
            }
        }

        return L3;
    }
}