Merging two arraylists without creating third one

Question

Here is one task, i was trying to solve. You must write the function

void merge(ArrayList a, ArrayList b)  {
// code
}

The function recieves two ArrayLists with equal size as input parameters [a1, a2, ..., an], [b1, b2, ..., bn]. The execution result is the 1st ArrayList must contain elements of both lists, and they alternate consistently ([a1, b1, a2, b2, ..., an, bn]) Please read the bold text twice =)

Code must work as efficiently as possible.

Here is my solution

public static void merge(ArrayList a, ArrayList b) {
ArrayList result = new ArrayList();
int i = 0;

Iterator iter1 = a.iterator();
Iterator iter2 = b.iterator();
while ((iter1.hasNext() || iter2.hasNext()) && i < (a.size() + b.size())) {
    if (i % 2 ==0) {
        result.add(iter1.next());
    } else {
        result.add(iter2.next());
    }
    i++;
}

a = result;

}

I know it's not perfect at all. But I can't understand how to merge in the 1st list without creating tmp list.

Thanks in advance for taking part.

You haven't asked us a question. "Here is my assignment; do it for me" doesn't count. — user2357112, Jan 21 '16 at 21:56
Possible duplicate of [Write a method that merges two array lists, alternating elements from both array lists](http://stackoverflow.com/questions/16165942/write-a-method-that-merges-two-array-lists-alternating-elements-from-both-array) — miken32, Jan 21 '16 at 22:44

John Sensebe · Accepted Answer · 2016-01-21T22:23:48.747

0

Double ArrayList a's size. Set last two elements of a to the last element of the old a and the last element of b. Keep going, backing up each time, until you reach the beginnings of a and b. You have to do it from the rear because otherwise you will write over the original a's values.

edited Jan 21 '16 at 22:23

answered Jan 21 '16 at 21:59

John Sensebe

1,386
8
11

Thanks, John ! Solution is so simple ! As always. – SergeBud Jan 21 '16 at 23:13

score 0 · Answer 2 · answered Jan 21 '16 at 23:26

In the end i got this:

public static void merge(ArrayList<Integer> arr1, ArrayList<Integer> arr2) {
        int indexForArr1 = arr1.size() - 1;
        int oldSize = arr1.size();
        int newSize = arr1.size() + arr2.size();

        /*
            decided not to create new arraylist with new size but just to fill up old one with nulls
         */
        fillWithNulls(arr1, newSize);

        for(int i = (newSize-1); i >= 0; i--) {
            if (i%2 != 0) {
                int indexForArr2 = i%oldSize;
                arr1.set(i,arr2.get(indexForArr2));
                oldSize--; // we reduce the size because we don't need tha last element any more
            } else {
                arr1.set(i, arr1.get(indexForArr1));
                indexForArr1--;
            }
        }
    }

    private static void fillWithNulls(ArrayList<Integer> array, int newSize) {
        int delta = newSize - array.size();
        for(int i = 0; i < delta; i++) {
            array.add(null);
        }
    }

Thanks John again for bright idea!

It'd be a little more efficient to use `oldSize - 1` in your `for` loop and set elements `i * 2` and `i * 2 + 1` of `arr1` in each iteration. You'd get rid of the two `%`s and the `if` that way. And use `ArrayList.ensureCapacity` to efficiently allocate memory for the larger `arr1`. — John Sensebe, Jan 22 '16 at 00:02
i'll try to replace oldsize var later ArrayList.ensureCapacity is obvious, again) — SergeBud, Jan 22 '16 at 06:36
Only now I remembered about put(index, object) method in List collection — SergeBud, Jul 07 '16 at 07:37

Merging two arraylists without creating third one

2 Answers2