import java.util.Scanner;

public class MergeLists {
  public static void main (String[] args) {
    List<Integer> l = new List<Integer>();
    List<Integer> m = new List<Integer>();
    Scanner scanner = new Scanner(System.in);

    for (String s: scanner.nextLine().split(" ")) {
      l.insert(Integer.parseInt(s));
    }

    for (String s: scanner.nextLine().split(" ")) {
      m.insert(Integer.parseInt(s));
    }

    /*
    for (int i = 0; i < 12; ++i) {
      l.delete(i);
      m.delete(i);
    }
    System.out.println(l.toString());
    System.out.println(m.toString());
    */

    List<Integer> n = merge(l, m);
    System.out.println(n.toString());
  }

  /**
   *
   */
  public static <T extends Comparable<T>> List<T> merge(List<T> l, List<T> m) {
    List<T> result = new List<T>();
    List<T>.Node<T> lcurrent = l.getHead();
    List<T>.Node<T> mcurrent = m.getHead();
    List<T>.Node<T> tmp = null;

    // insert in this specific case takes O(1) since the tail is checked upfront
    // in the insert method and we simply append it as new tail
    while (lcurrent != null || mcurrent != null) {
      if (lcurrent == null || mcurrent == null) {
        tmp = (lcurrent == null ? mcurrent : lcurrent);
        result.insert(tmp.data);
        tmp = tmp.next;
        
        if (lcurrent == null) {
          mcurrent = tmp;
        } else {
          lcurrent = tmp;
        }

        continue;
      }

      if (lcurrent.compareTo(mcurrent) >= 0) {
        result.insert(mcurrent.data);
        mcurrent = mcurrent.next;
      } else {
        result.insert(lcurrent.data);
        lcurrent = lcurrent.next;
      }
    }

    return result;
  }
}

@@ -673,16 +673,70 @@
 /**%0A   *
+  Needs constant additional memory (three references).
 %0A   */%0A 
@@ -810,24 +810,1641 @@
 ist%3CT%3E m) %7B%0A
+    // last element of the first list is smaller than the first element of the%0A    // second list =%3E simply manipulate the references; no additional memory used%0A    if (l.getTail().compareTo(m.getHead()) %3C= 0) %7B%0A      l.getTail().next = m.getHead();%0A      l.setTail(m.getTail());%0A      return l;%0A    %7D%0A%0A    // last element of the second list is smaller than the first element of the%0A    // first list =%3E simply manipulate the references; no additional memory used%0A    if (m.getTail().compareTo(l.getHead()) %3C= 0) %7B%0A      m.getTail().next = l.getHead();%0A      m.setTail(l.getTail());%0A      return m;%0A    %7D%0A%0A    // otherwise =%3E general merge%0A    List%3CT%3E.Node%3CT%3E lcurrent = l.getHead();%0A    List%3CT%3E.Node%3CT%3E mcurrent = m.getHead();%0A    List%3CT%3E.Node%3CT%3E previous = null;%0A%0A    while (lcurrent != null %7C%7C mcurrent != null) %7B%0A      if (lcurrent == null %7C%7C mcurrent == null) %7B%0A        break;%0A      %7D%0A%0A      if (lcurrent.compareTo(mcurrent) %3C= 0) %7B%0A        while (lcurrent != null && lcurrent.compareTo(mcurrent) %3C= 0) %7B%0A          previous = lcurrent;%0A          lcurrent = lcurrent.next;%0A        %7D%0A%0A        previous.next = mcurrent;%0A      %7D else if (mcurrent.compareTo(lcurrent) %3C= 0) %7B%0A        while (mcurrent != null && mcurrent.compareTo(lcurrent) %3C= 0) %7B%0A          previous = mcurrent;%0A          mcurrent = mcurrent.next;%0A        %7D%0A%0A        previous.next = lcurrent;%0A      %7D%0A    %7D%0A%0A    return (l.getHead().compareTo(m.getHead()) %3C 0 ? l : m);%0A  %7D%0A%0A  /**%0A   *  Needs (n + m) additional memory for two lists of size n and m, respectively.%0A   */%0A  public static %3CT extends Comparable%3CT%3E%3E List%3CT%3E merge2(List%3CT%3E l, List%3CT%3E m) %7B%0A
     List%3CT%3E 

Implement merge version which uses only a constant amount of additional memory