interleave

Write a static method interleave that takes two arrays
   of integers as parameters and that returns a new array that contains the
   result of interleaving the elements of the two arrays.  It should not alter
   either of its parameters.  Two arrays are interleaved by taking elements in
   the following order:

        1st element of 1st list
        1st element of 2nd list
        2nd element of 1st list
        2nd element of 2nd list
        3rd element of 1st list
        3rd element of 2nd list
        and so on
        
   For example, if the variables list1 and list2 contain the following values:

        list1: (1, 8, 3, 9)
        list2: (2, 12, 6, 14)

   Then the call interleave(list1, list2) should return a new array that stores
   the following values:

        (1, 2, 8, 12, 3, 6, 9, 14)

   The order of the parameters matters.  For example, interleave(list2, list1)
   should produce the following array as its result:

        (2, 1, 12, 8, 6, 3, 14, 9)

   One list might be longer than the other, in which case any extra values from
   the longer list should simply be appended at the end of the result.  For
   example, given the following lists:

        list1: (1, 8, 3, 9)
        list2: (82, 7, 4, 2, 1, 6, 5, 0, 18)

   The call interleave(list1, list2) should produce the following result:

        (1, 82, 8, 7, 3, 4, 9, 2, 1, 6, 5, 0, 18)

   Notice that the first four values of the two arrays have been interleaved
   and the excess values from the second list (1, 6, 5, 0, 18) have been
   included at the end of the result.  In this case the second list was longer,
   but it could be the case that the first list is longer.  Either list could
   also be empty, in which case the result should contain the values from the
   other list.  Notice that your method is to return a new array.

   Write your solution to interleave below.