Блог

Метод, который я использую, принимает два отсортированных списка и возвращает единый список, содержащий все элементы в двух исходных списках в отсортированном порядке.

Например, если исходными списками являются (1, 4, 5) и (2, 3, 6), то результирующий список будет (1, 2, 3, 4, 5, 6).

Есть ли что-то, чего мне не хватает?

 public static<E extends Comparable<E>> List<E> mergeSortedLists(List<E> a, List<E> b) {
    List<E> result = new ArrayList<E>();

    PushbackIterator<E> aIter = new PushbackIterator<E>(a.iterator());
    PushbackIterator<E> bIter = new PushbackIterator<E>(b.iterator());

    while (aIter.hasNext() amp;amp; bIter.hasNext()) {
        if (aIter.next().compareTo(bIter.next()) < 0) {
            result.add(aIter.next());
        }  
        if (bIter.next().compareTo(bIter.next()) > 0){
            result.add(bIter.next());
        }
    }
    while (aIter.hasNext()) {
        result.add(aIter.next());
    }
    while (bIter.hasNext()) {
        result.add(bIter.next());
    }
    return resu<
}
  

Чтобы выполнить слияние, вам нужно просмотреть следующее значение, чтобы увидеть, какое следующее значение использовать.

В конце концов, в одном из списков закончатся значения раньше, чем в другом, поэтому вам нужно проверить это.

Одна хитрость заключается в использовании null в качестве маркера конца данных, предполагая, что списки не могут содержать null значения, что является справедливым предположением, поскольку они должны быть отсортированы. В этом случае код будет выглядеть следующим образом:

 public static <E extends Comparable<E>> List<E> mergeSortedLists(List<E> list1, List<E> list2) {
    List<E> merged = new ArrayList<>(list1.size()   list2.size());

    // Get list iterators and fetch first value from each, if available
    Iterator<E> iter1 = list1.iterator();
    Iterator<E> iter2 = list2.iterator();
    E value1 = (iter1.hasNext() ? iter1.next() : null);
    E value2 = (iter2.hasNext() ? iter2.next() : null);

    // Loop while values remain in either list
    while (value1 != null || value2 != null) {

        // Choose list to pull value from
        if (value2 == null || (value1 != null amp;amp; value1.compareTo(value2) <= 0)) {

            // Add list1 value to result and fetch next value, if available
            merged.add(value1);
            value1 = (iter1.hasNext() ? iter1.next() : null);

        } else {

            // Add list2 value to result and fetch next value, if available
            merged.add(value2);
            value2 = (iter2.hasNext() ? iter2.next() : null);

        }
    }

    // Return merged result
    return merged;
}
  

Тест

 System.out.println(mergeSortedLists(Arrays.asList(1, 4, 5),
                                    Arrays.asList(2, 3, 6)));
  

Вывод

 [1, 2, 3, 4, 5, 6]
  

Я собираюсь предположить, что вы намеревались сделать что-то подобное при использовании PushbackIterator :

 while (aIter.hasNext() amp;amp; bIter.hasNext()) {
    E aElem = aIter.next();
    E bElem = bIter.next();
    if (aElem.compareTo(bElem) <= 0) {
        result.add(aElem);
        bIter.pushback(bElem);
    } else {
        result.add(bElem);
        aIter.pushback(aElem);
    }
}
  

Тот же подход к объединению 2 массивов также может быть использован с небольшой настройкой итераторов. при необходимости вы можете использовать добавление элементов вместо печати.

 static void printItr(Iterator<String> it1, Iterator<String> it2) {
    String firstString=null,secondString = null;
    boolean moveAheadIt1 = true, moveAheadIt2 = true;

    while(it1.hasNext() amp;amp; it2.hasNext()){
         firstString = moveAheadIt1 ? it1.next() : firstString ;
         secondString = moveAheadIt2 ? it2.next() : secondString;

         if(firstString.compareTo(secondString) < 0){
            System.out.println(firstString);
            moveAheadIt2 = false;
            moveAheadIt1 = true;
        }else {
            System.out.println(secondString);
            moveAheadIt1 = false;
            moveAheadIt2 = true;
        }
    }

    while(it1.hasNext()){
        System.out.println(it1.next());
    }
    while(it2.hasNext()){
        System.out.println(it2.next());
    }

}
  

Если вы хотите использовать библиотеку, самым чистым решением было бы использовать Collection-utils 4 и IteratorUtils.collatedIterator().

Вам необходимо предоставить компаратор, чтобы выбрать правильный элемент.