import java.util.*;

public class ListMerge {
  // This class contains two different example merge methods
  // that use iterators to traverse the lists.
  // Note that Java's built-in LinkedList class is used.
  // Both methods assume that the lists are sorted, and that each
  // list contains no duplicate items.
  
  // This merge method assumes that the provided list contains
  // Integer objects.
  static LinkedList mergeIntList(LinkedList l1, LinkedList l2) {
    LinkedList result = new LinkedList();
    Iterator it1 = l1.iterator();
    Iterator it2 = l2.iterator();
    boolean use1 = it1.hasNext();
    boolean use2 = it2.hasNext();
    int n1 = 0;
    int n2 = 0;
    if (use1) n1 = ((Integer) it1.next()).intValue();
    if (use2) n2 = ((Integer) it2.next()).intValue();		 
    while (use1 || use2) {
      if (use1 && n1 == n2) {
        result.addLast(new Integer(n1));
        use1 = it1.hasNext();
        use2 = it2.hasNext();
        if (use1) n1 = ((Integer) it1.next()).intValue();
        if (use2) n2 = ((Integer) it2.next()).intValue();
      } else if (use1 && (!use2 || n1 < n2)) {
        result.addLast(new Integer(n1));
        use1 = it1.hasNext();
        if (use1) n1 = ((Integer) it1.next()).intValue();
      } else if (use2) {
        result.addLast(new Integer(n2));
        use2 = it2.hasNext();
        if (use2) n2 = ((Integer) it2.next()).intValue();
      }
    }
    return result;
  }
  
  // This merge method assumes that the list can contain any object
  // that implement the Comparable interface, meaning that they have
  // a compareTo method that compares the object to a parameter and
  // returns a negative int if the parameter is "smaller,"
  // returns a positive int if the parameter is "greater," and
  // returns zero if the two objects are considered "equal."
  static LinkedList mergeObjectList(LinkedList l1, LinkedList l2) {
    LinkedList result = new LinkedList();
    Iterator it1 = l1.iterator();
    Iterator it2 = l2.iterator();
    Comparable n1 = null;
    Comparable n2 = null;
    if (it1.hasNext()) n1 = (Comparable) it1.next();
    if (it2.hasNext()) n2 = (Comparable) it2.next();	 
    while (n1 != null || n2 != null) {
      if (n1 != null && n1.equals(n2)) {
        result.addLast(n1);
        if (it1.hasNext()) n1 = (Integer) it1.next(); else n1 = null;
        if (it2.hasNext()) n2 = (Integer) it2.next(); else n2 = null;
      } else if (n1 != null  && 
                 (n2 == null || n1.compareTo(n2) < 0)) {
        result.addLast(n1);
        if (it1.hasNext()) n1 = (Integer) it1.next(); else n1 = null;
      } else if (n2 != null) {
        result.addLast(n2);
        if (it2.hasNext()) n2 = (Integer) it2.next(); else n2 = null;
      }
    }
    return result;
  }

  public static void main(String[] args) {
    LinkedList l1 = new LinkedList();
    l1.addLast(new Integer(2));	
    l1.addLast(new Integer(4));
    l1.addLast(new Integer(5));
    l1.addLast(new Integer(9));
    
    LinkedList l2 = new LinkedList();
    l2.addLast(new Integer(3));	
    l2.addLast(new Integer(5));
    l2.addLast(new Integer(7));
    l2.addLast(new Integer(8));
    l2.addLast(new Integer(11));
    
    LinkedList l3 = mergeIntList(l1,l2);
    Iterator it = l3.iterator();
    while (it.hasNext())
      System.out.println(it.next());
    System.out.println("done with the first test");
    
    LinkedList l4 = mergeObjectList(l1,l2);
    it = l4.iterator();
    while (it.hasNext())
      System.out.println(it.next());
    System.out.println("done with the second test");	
  }
}