Есть два ArrayList одинакового размера list1(1,2,3) и list2(4,5,6).
нужно записать в list1 эл-ты двух листов , которые идут последовательно [1,4,2,5,3,6].
Причем нужна высокая эффективность алгоритма.

эффективность алгоритма O(n) нужна

У меня в задаче были именно Arraylist.

т.е. эффективность этого алгоритма O(n) ?
Может кто-нибудь объяснить почему эффективность равна O(n)?
мы ведь пробегаем по всем элементам n и при добавлении тоже эл-ты сдвигаются

да я упустил.. это перемешивание должно быть в методе, который возвращает void .
И получается 3 массив мы уже не заведем

Роман_мск77Вот такой есть вариант:
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class TestOne {
public static void main(String[] args) {
List<Long> oneList = new ArrayList<Long>();
List<Long> twoList = new ArrayList<Long>();
List<Long> includeList = new ArrayList<Long>();
oneList.add(1L);
oneList.add(2L);
oneList.add(3L);

twoList.add(4L);
twoList.add(5L);
twoList.add(6L);

Iterator<Long> iter = oneList.iterator();
while(iter.hasNext()) {
Long tmp = iter.next();
includeList.add(tmp);
iter.remove();
Iterator<Long> iter2 = twoList.iterator();
while(iter2.hasNext()) {
Long tmp2 = iter2.next();
includeList.add(tmp2);
iter2.remove();
break;
}
}
System.out.println("========>"+includeList.toString());
}

}



Результат
========>[1, 4, 2, 5, 3, 6]

так эффективность алгоримта будет O(n*n) . нужна O(n)