Как объединить два упорядоченных списка объектов?

Question

public  class ListMerge
{
   public static void main( String[] args) 
   {

      Scanner input = new Scanner(System.in);

      System.out.println ("Input length of arraylist 1:");
      int n = input.nextInt();
      ArrayList x = new ArrayList();
      ArrayList y = new ArrayList();
      for (int i = 0; i < n; i++)
      {
        System.out.println ("Input x[ " + i +"] :" );
         x.add(new Integer(i));

      }


      System.out.println ("Input length of arraylist 2:");
      int m = input.nextInt();


      for (int i = 0; i < m; i++)
      {
        System.out.println ("Input y[ " + i +"] :" );
        y.add(new Integer(i));

      }
      List<Integer> all = new ArrayList<Integer>();

      all.addAll(x);
      all.addAll(y);
      System.out.println(all);


  }
}

Я сделал это но он не принимает значения от пользователя. пожалуйста скажите мне, почему ....

Answer 1

Прямо из Википедии :

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    end while
    if length(left) > 0 
        append left to result
    else  
        append right to result
    return result

Answer 2

С Google Guava :

Iterable<Integer> all = 
    Iterables.mergeSorted(ImmutableList.of(x, y), Ordering.natural());
System.out.println(all);

Answer 3

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

public static <T, C extends Comparator<T>> List<T> mergeOrderedAscending( List<T> list0,  List<T> list1, C c)
{
    if(list0 == null || list1 == null || c == null)
        throw new IllegalArgumentException("null parameter");

    Iterator<T> it0 = list0.iterator();
    Iterator<T> it1 = list1.iterator();

    List<T> result = new ArrayList<T>(list0.size() + list1.size());


    T i0 = null;
    T i1 = null;


    if(it0.hasNext())
        i0 = it0.next();
    else
        i0 = null;


    if(it1.hasNext())
        i1 = it1.next();
    else
        i1 = null;

    while (i0 != null && i1 != null) {

        if (c.compare(i0, i1) < 0) {
            result.add(i0);

            if(it0.hasNext())
                i0 = it0.next();
            else
                i0 = null;

        }
        else {
            result.add(i1);

            if(it1.hasNext())
                i1 = it1.next();
            else
                i1 = null;
        }
    } 


    if (i0 != null) {

        do {
            result.add(i0);

            if(it0.hasNext())
                i0 = it0.next();
            else
                i0 = null;
        } while(i0 != null);
    }
    else if (i1 != null) {
        do {
            result.add(i1);

            if(it1.hasNext())
                i1 = it1.next();
            else
                i1 = null;
        } while(i1 != null);
    }

    return result;
}

Answer 4

Чтобы завершить круг знаний, вот реализация ответов @ unbeli's / Wikipedia.

public List<T> mergeOrdered(final List<T> list0, final List<T> list1) {
    List<T> result = new ArrayList<T>();

    while (list0.size() > 0 && list1.size() > 0) {
    if (list0.get(0).compareTo(list1.get(0)) < 0) {
            result.add(list0.get(0));
            list0.remove(0);
        }
        else {
            result.add(list1.get(0));
            list1.remove(0);
        }
    }

    if (list0.size() > 0) {
        result.addAll(list0);
    }
    else if (list1.size() > 0) {
        result.addAll(list1);
    }

    return result;
}

Обратите внимание, что списки, созданные с использованием Arrays.asList(), приведут к массиву фиксированной длины , из которого элементы не могут быть удалены, поэтому убедитесь, что вы передаете динамические списки!

public List<T> buildDynamicListFromArray(final T[] arr0) {
    List<T> result = new ArrayList<T>();
    int len = arr0.length;
    for (int i = 0; i < len; i++) {
        result.add(arr0[i]);
    }
    return result;
}