interface List<E> {
  public E getHead();
  public List<E> getTail();
  public boolean isEmpty();
  public String toString();
}

class NullList<E> implements List<E> {
  public E getHead() {
    throw new Error("The null list has no head");
  }
  public List<E> getTail() {
    throw new Error("The null list has no tail");
  }
  public boolean isEmpty() {
    return true;
  }
  public String toString() {
    return "";
  }
}

class NodeList<E> implements List<E> {
  private E head;
  private List<E> tail;
  public NodeList(E e, List<E> t) {
    head = e;
    tail = t;
  }
  public E getHead() {
    return head;
  }
  public List<E> getTail() {
    return tail;
  }
  public boolean isEmpty() {
    return false;
  }
  public String toString() {
    return head + " " + tail.toString();
  }
}

public class Append {
  // The procedural approach. Notice how the implementation of this method tells
  // HOW to append the lists:
  public static <E> List<E> appendImp(List<E> l1, List<E> l2) {
    List<E> invl = new NullList<E>();
    List<E> lr = l2;
    // Invert the list l1 to produce the list invl:
    while (!l1.isEmpty()) {
      invl = new NodeList<E>(l1.getHead(), invl);
      l1 = l1.getTail();
    }
    // append the inverted list, from tail to head, into l2.
    while (!invl.isEmpty()) {
      lr = new NodeList<E>(invl.getHead(), lr);
      invl = invl.getTail();
    }
    return lr;
  }

  // The declarative approach. Notice how the implementation of this method
  // tells WHAT the appended list is like.
  public static <E> List<E> appendFunc(List<E> l1, List<E> l2) {
    if (l1.isEmpty()) {
      return l2;
    } else {
      return new NodeList<E>(l1.getHead(), appendFunc(l1.getTail(), l2));
    }
  }

  public static void main(String args[]) {
    List<Integer> l1 = new NullList<Integer>();
    for (int i = 10; i > 0; i--) {
      l1 = new NodeList<Integer>(i, l1);
    }
    System.out.println(l1);
    List<Integer> l2 = new NullList<Integer>();
    for (int i = 20; i > 10; i--) {
      l2 = new NodeList<Integer>(i, l2);
    }
    System.out.println(l2);
    System.out.println(appendFunc(l1, l2));
  }
}