import java.io.*;
import java.lang.*;
import java.util.*;

// \esc{Listes Ge'ne'riques comme en C}
// \esc{De'claration des listes, voir page \pageref{prog:declaration-liste}} 

public class Liste {

  Object contenu;
  Liste suivant;

  Liste (Object x, Liste a) {
      contenu = x;
      suivant = a;
  }

  static Liste ajouter (Object x, Liste a) {

    return new Liste (x, a);
  }

  static int longueur(Liste a) {
  // \esc{Longueur d'une liste, voir page \pageref{prog:longueur-liste-rec}}

    if (a == null)
        return 0;
    else
        return 1 + longueur (a.suivant);
  }

  static Liste cons (Object x, Liste a) {

    return new Liste (x, a);
  }

  static Object head (Liste a) {
    //\esc{Tail  voir page  \pageref{prog:tail}} 

    if (a == null) {
        System.err.println("Head d'une liste vide.\n");
        System.exit (1);
    }
    return a.contenu;
  }

  static Liste tail (Liste a) {
    //\esc{Tail  voir page  \pageref{prog:tail}} 

    if (a == null) {
        System.err.println("Tail d'une liste vide.\n");
        System.exit (1);
    }
    return a.suivant;
  }

  static Liste append (Liste a, Liste b) {
  //\esc{ Append et Nconc voir page \pageref{prog:append}} 

    if (a == null)
        return b;
    else
        return ajouter (a.contenu, append (a.suivant, b)) ;
  }

  static Liste nConc (Liste a, Liste b) {

    Liste     c;
    
    if (a == null) 
        return b;
    else {
        c = a;
        while (c.suivant != null) 
             c = c.suivant; 
        c.suivant = b;
        return a;
    }
  }

  static Liste nReverse (Liste a) {
  // \esc{Nreverse et Reverse, voir page \pageref{prog:reverse}} */

    Liste b, c;

    b = null;
    while (a != null) {
        c = a.suivant;
        a.suivant = b;
        b = a;
        a = c;
    }
   return b;
  }

  static Liste reverse (Liste a) {

     if (a == null)
         return  a;
     else
         return  append (reverse (a.suivant), 
                         ajouter ((a.contenu), null));
  } 

  static void imprimer (Liste a) {

    for (Liste b = a; b != null; b = b.suivant) 
        System.out.print (b.contenu + " ");
    System.out.println ();
  }

  static void imprimerPrefixe (int n, Liste a) {

    int i = 0;
    for (Liste b = a; b != null && i < n; b = b.suivant) { 
        System.out.print (b.contenu + " ");
        ++i;
    }
    System.out.println ();
  }

}

public class ListeAndInt {

  static Liste ajouter (int v, Liste a) {
     return new Liste (new Integer(v), a);
  }

  static int intHead (Liste a) {
     return ((Integer)(a.contenu)).intValue();
  }

  static Liste inserer (int v, Liste a) {
  // \esc{Insert, voir page \pageref{prog:insert}}

    Liste b = a;
    while (b.suivant != a && v > intHead(b.suivant))
        b = b.suivant;
    b.suivant = ajouter (v, b.suivant);        
    a.contenu = new Integer (intHead(a) + 1);
    return a;
 }   

  public static void main(String args[]) {
      
    Liste a, b, c, d, e;
    a =  ajouter(8, ajouter (6, ajouter (4, ajouter (2, null))));
    Liste.imprimer (a);
    System.out.println (Liste.longueur (a));
    b = ajouter (14, ajouter (12, ajouter (10, null)));
    Liste.imprimer (b);    
    c = Liste.append (a, b);
    Liste.imprimer (c);    
    d = Liste.reverse (c);
    Liste.imprimer (c);
    Liste.imprimer (d);
    d = Liste.nReverse (c);
    Liste.imprimer (c);
    Liste.imprimer (d);
    // avec les entiers
    int n;
    a = ajouter(8, ajouter (6, ajouter (4, ajouter (2, null))));
    b = ajouter (14, ajouter (12, ajouter (10, null)));
    e = Liste.reverse (Liste.append (b, a));
    n = Liste.longueur (e);
    e = ajouter (n, e);
    e = Liste.nConc (e, e);
    Liste.imprimerPrefixe (n + 5, e);
    e = inserer (7, e);
    Liste.imprimerPrefixe (n + 5, e);
  }
}