Write a method that merges two array lists, altern

Question

Write a method

public static ArrayList merge(ArrayList a, ArrayList b)

that merges two array lists, alternating elements from both array lists. If one array list is shorter than the other, then alternate as long as you can and then append the remaining elemts from the longer array list. For example, if a is

1 4 9 16

and b is

9 7 4 9 11

then merge returns the array list

1 9 4 7 9 4 16 9 11

---

What I tried doing was writing a for loop with if statements such that a number is added to the merge array list from array list a when i is an even number (i%2==0) and from array list b when i is an odd number. I am however not sure how to deal with the fact that one array list can be longer than the other. Could anyone please help me out?

EDIT: Ok, here is the code (but it is far from correct):

public static ArrayList<Integer> merge(ArrayList<Integer> een, ArrayList<Integer> twee)
{
    ArrayList<Integer> merged = new ArrayList<Integer>();

    for(int i = 0; i<100; i++)
    {           
        if(i%2!=0)
        {
            merged.add(a.get(i));
        }   
        if(i%2 == 0)
        {
            merged.add(b.get(i));
        }               
    }

    System.out.println(merged);
    return merged;
}

Answer 1

I have done this in the following way in php:

<?php
    $list1 = array("a","b","c");
    $list2 = array(1,2,3);
    $list3 = array();
    $j=0;
    $k=0;

    for($i=0;$i<6;$i++)
    {
        if($i%2==0)
        {
            $list3[$i]=$list1[$j];
            $j++;
        }

        else
        {
            $list3[$i]=$list2[$k];
            $k++;
        }

        echo $list3[$i]."<br>";
    }
?>

Answer 2

You don't need to check modulo, or you'll skip every second element from each input list.

public static <E> List<E> merge(List<E> een, List<E> twee) {
    List<E> merged = new ArrayList<E>(een.size() + twee.size());
    List<E> shorter = een.size() <= twee.size() ? een : twee;
    List<E> longer = een.size() > twee.size() ? een : twee;
    for (int i = 0; i < shorter.size(); i++) {
        merged.add(een.get(i));
        merged.add(twee.get(i));
    }
    for (int i = shorter.size(); i < longer.size(); i++) {
        merged.add(longer.get(i));
    }
    return merged;
}

This generic version works for all kind of Lists and generic types.

Answer 3

Iterators seem to do the trick most easily

public static <T> ArrayList<T> merge(Collection<T> a, Collection<T> b) {
    Iterator<T> itA = a.iterator();
    Iterator<T> itB = b.iterator();
    ArrayList<T> result = new ArrayList<T>();

    while (itA.hasNext() || itB.hasNext()) {
        if (itA.hasNext()) result.add(itA.next());
        if (itB.hasNext()) result.add(itB.next());
    }

    return result;
}

Without iterators:

public static <T> ArrayList<T> merge(List<T> a, List<T> b) {
    ArrayList<T> result = new ArrayList<T>();
    int size = Math.max(a.size(), b.size());

    for (int i = 0; i < size; i++) {
        if (i < a.size()) result.add(a.get(i));
        if (i < b.size()) result.add(b.get(i));
    }

    return result;
}

Note, I've relaxed the method signature a bit. If you're implementing the merging using iterators, Collection (or even Iterable) will do. Otherwise, List will do. There is no need to require ArrayList as a method argument type

Answer 4

I had the same situation and below was my solution:

// array list to hold the merged list
ArrayList<Integer> mergedList = new ArrayList<Integer>();

// Get the bigger size
int maxSize = listOne.size() > listTwo.size() ? listOne.size() : listTwo.size();

// Loop thru the list
for( int i = 0; i <= maxSize; i++){
    // We need to check first if index exist then just add it to mergeList
    if( i < listOne.size() ) mergedList.add( listOne.get( i ) );
    // We need to check first if index exist then just add it to mergeList
    if( i < listTwo.size() ) mergedList.add( listTwo.get( i ) );
}