java - 使用迭代器合并列表

Question

我需要在 java 中合并两个字符串列表，但我不太确定最好的方法。我必须使用迭代器和 compareTo() 方法。例如……

示例:L1:A、B、C、D L2:B、D、F、G 结果:A、B、B、C、D、D、F、G

我可以假设输入列表已经排序并且我不能使用 contains() 方法。我进行了一些初步检查，但我坚持使用 while 循环。

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?
}

如有任何帮助，我们将不胜感激。

Answer 1

如果您只使用变量来保存每个迭代器的当前值，那就相当简单了。此解决方案假定您的列表不包含 null，但添加空值处理并不困难，因为列表已排序。

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;
    }
}