Question: The method I am using takes two sorted lists and returns a single list containing all of the elements in the two original lists, in sorted order.

For example, if the original lists are (1, 4, 5) and (2, 3, 6) then the result list would be (1, 2, 3, 4, 5, 6). 

Is there something I am missing? 

```
public static<E extends Comparable<E>> List<E> mergeSortedLists(List<E> a, List<E> b) {
    List<E> result = new ArrayList<E>();

    PushbackIterator<E> aIter = new PushbackIterator<E>(a.iterator());
    PushbackIterator<E> bIter = new PushbackIterator<E>(b.iterator());

    while (aIter.hasNext() && bIter.hasNext()) {
        if (aIter.next().compareTo(bIter.next()) < 0) {
            result.add(aIter.next());
        }  
        if (bIter.next().compareTo(bIter.next()) > 0){
            result.add(bIter.next());
        }
    }
    while (aIter.hasNext()) {
        result.add(aIter.next());
    }
    while (bIter.hasNext()) {
        result.add(bIter.next());
    }
    return result;
}

```

Answer: 
In order to perform a merge, you need to peek at the next value, so see which next value to use.

Eventually, one of the lists will run out of values before the other, so you need to check for that.

One trick is to use `null` as an End-Of-Data marker, assuming that lists cannot contain `null` values, which is a fair assumption since they have to be sorted. In that case, code will be like this:

```
public static <E extends Comparable<E>> List<E> mergeSortedLists(List<E> list1, List<E> list2) {
    List<E> merged = new ArrayList<>(list1.size() + list2.size());

    // Get list iterators and fetch first value from each, if available
    Iterator<E> iter1 = list1.iterator();
    Iterator<E> iter2 = list2.iterator();
    E value1 = (iter1.hasNext() ? iter1.next() : null);
    E value2 = (iter2.hasNext() ? iter2.next() : null);

    // Loop while values remain in either list
    while (value1 != null || value2 != null) {

        // Choose list to pull value from
        if (value2 == null || (value1 != null && value1.compareTo(value2) <= 0)) {

            // Add list1 value to result and fetch next value, if available
            merged.add(value1);
            value1 = (iter1.hasNext() ? iter1.next() : null);

        } else {

            // Add list2 value to result and fetch next value, if available
            merged.add(value2);
            value2 = (iter2.hasNext() ? iter2.next() : null);

        }
    }

    // Return merged result
    return merged;
}

```

*Test*

```
System.out.println(mergeSortedLists(Arrays.asList(1, 4, 5),
                                    Arrays.asList(2, 3, 6)));

```

*Output*

```
[1, 2, 3, 4, 5, 6]

```
I'm going to assume you intended something like this with your use of `PushbackIterator`:

```
while (aIter.hasNext() && bIter.hasNext()) {
    E aElem = aIter.next();
    E bElem = bIter.next();
    if (aElem.compareTo(bElem) <= 0) {
        result.add(aElem);
        bIter.pushback(bElem);
    } else {
        result.add(bElem);
        aIter.pushback(aElem);
    }
}

```