const
   array_max_size=10;
type
   tipo_elemento=integer;
   tipo_vettore=array[1..array_max_size] of tipo_elemento;
   tipo_lista=^cella;
   cella=   record
               element:tipo_elemento;
               next:tipo_lista
            end;

procedure crea_vettore_random(var V:tipo_vettore);

var
   i:integer;
begin
   Randomize;
   for i:= array_max_size downto 1 do
      V[i]:=Random(10);
end;

procedure inserisci_in_coda_ric(x:tipo_elemento;var L:tipo_lista);

begin
   if(L=nil)then
      begin
         new(L);
         L^.element:=x;
         L^.next:=nil;
      end
   else
      inserisci_in_coda_ric(x,L^.next)
end;

procedure inserisci_in_coda_it(x:tipo_elemento;var L:tipo_lista);

var
   prec,p,tmp:tipo_lista;
begin
   if(L=nil)then
      begin
         new(L);
         L^.element:=x;
         L^.next:=nil
      end
   else
      begin
         p:=l;
         while(p<>nil)do
            begin
               prec:=p;
               p:=p^.next
            end;
         new(tmp);
         tmp^.element:=x;
         tmp^.next:=nil;
         prec^.next:=tmp;
         p:=prec
      end
end;

procedure leggi_lista_da_vettore(var V:tipo_vettore;var L:tipo_lista);

var
   i:integer;
begin
   for i:=1 to array_max_size do
      inserisci_in_coda_it(V[i],L)
end;

procedure stampa_lista(L:tipo_lista);

begin
   if(L=nil)then
      writeln('nil')
   else
      begin
         write(L^.element,' ');
         stampa_lista(L^.next)
      end
end;


procedure leggi_lista_da_tastiera(var L:tipo_lista);

var
   x:tipo_elemento;
begin
   if(eoln)then
      L:=nil
   else
begin
      readln(x);
      inserisci_in_coda_ric(x,L);
      leggi_lista_da_tastiera(L^.next)
   end
end;

function lunghezza_lista_ric(L:tipo_lista):integer;

begin
   if(L=nil)then
      lunghezza_lista_ric:=0
   else
      lunghezza_lista_ric:=lunghezza_lista_ric(L^.next)+1
end;

function lunghezza_lista_it(L:tipo_lista):integer;

var
   i:integer;
begin
   i:=0;
   while(L<>nil)do
      begin
         inc(i);
         L:=L^.next
      end;
   lunghezza_lista_it:=i;
end;

function cerca_elemento_ric(x:tipo_elemento;L:tipo_lista):boolean;

begin
   if(L=nil)then
      cerca_elemento_ric:=false
   else if(L^.element=x)then
      cerca_elemento_ric:=true
   else
      cerca_elemento_ric:=cerca_elemento_ric(x,L^.next)
end;

function cerca_elemento_it(x:tipo_elemento;L:tipo_lista):boolean;

var
   trovato:boolean;
begin
   trovato:=false;
   while(L<>nil)and(not trovato)do
      begin
         trovato:=(L^.element=x);
         L:=L^.next
      end;
   cerca_elemento_it:=trovato
end;

procedure cancella_primo_ric(x:tipo_elemento;var L:tipo_lista);

var
   tmp:tipo_lista;
begin
   if(L<>nil)then
      if(L^.element<>x)then
         cancella_primo_ric(x,L^.next)
      else
         begin
            tmp:=L;
            L:=L^.next;
            dispose(tmp)
         end
end;

procedure cancella_primo_it(x:tipo_elemento;var L:tipo_lista);

var
   prec,p:tipo_lista;
begin
   if(L<>nil)and(L^.element=x)then
      begin
         p:=L;
         L:=L^.next;
         dispose(p)
      end;
   p:=L;
   while(p<>nil)and(p^.element<>x)do
      begin
         prec:=p;
         p:=p^.next
      end;
   if(p<>nil)then
      begin
         prec^.next:=p^.next;
         p:=prec^.next
      end
end;

procedure inserisci_in_testa(x:tipo_elemento;var L:tipo_lista);

var
   M:tipo_lista;
begin
   new(M);
   M^.element:=x;
   M^.next:=L;
   L:=M;
end;

procedure cancella_tutti_ric(x:tipo_elemento;var L:tipo_lista);

begin
   if(L<>nil)then
      if(L^.element=x)then
         begin
            L:=L^.next;
            cancella_tutti_ric(x,L)
         end
      else
         cancella_tutti_ric(x,L^.next)
end;

procedure cancella_tutti_it(x:tipo_elemento;var L:tipo_lista);

var
   prec,p:tipo_lista;
begin
   while(L<>nil)and(L^.element=x)do
      begin
         p:=L;
         L:=L^.next;
         dispose(p)
      end;
   p:=l;
   while(p<>nil)do
      begin
         if(P^.element<>x)then
            begin
               prec:=p;
               p:=p^.next
            end
         else
            begin
               prec^.next:=p^.next;
               dispose(p);
               p:=prec^.next
            end
      end
end;

procedure inverti_dispari(var L:tipo_lista);

var
   M:tipo_lista;
begin
   M:=nil;
   while(L<>nil)do
      begin
         inserisci_in_testa(L^.element,M);
         L:=L^.next;
         cancella_primo_ric(L^.element,L);
      end;
   L:=M;
end;

procedure inserisci_ord(x:tipo_elemento;var L:tipo_lista);

begin
   if(l=nil)then
      inserisci_in_testa(x,L)
   else if(x<L^.element)then
      inserisci_in_testa(x,L)
   else if(x>L^.element)then
      inserisci_ord(x,L^.next)
end;

function insert_head(x:tipo_elemento;L:tipo_lista):tipo_lista;

var
   M:tipo_lista;
begin
   new(M);
   M^.element:=x;
   M^.next:=L;
   insert_head:=M;
end;

function intersezione(L,M:tipo_lista):tipo_lista;

begin
   if((L=nil)or(M=nil))then
      intersezione:=nil
   else if(L^.element>M^.element)then
      intersezione:=intersezione(L,M^.next)
   else if(L^.element<M^.element)then
      intersezione:=intersezione(L^.next,M)
   else
      intersezione:=insert_head(L^.element,intersezione(L^.next,M^.next))
end;

function fondi(L,M:tipo_lista):tipo_lista;

begin
   if(L=nil)then
      fondi:=M
   else if(M=nil)then
      fondi:=L
   else if(L^.element<=M^.element)then
      begin
         L^.next:=fondi(L^.next,M);
         fondi:=L
      end
   else
      begin
         M^.next:=fondi(L,M^.next);
         fondi:=M
      end
end;

function split(L:tipo_lista):tipo_lista;

var pari:tipo_lista;
begin
   if(L=nil)then
      split:=nil
   else if(L^.next=nil)then
      split:=nil
   else
      begin
         pari:=L^.next;
         l^.next:=pari^.next;
         pari^.next:=split(pari^.next);
         split:=pari
      end
end;

procedure mergesort(var L:tipo_lista);

var
   pari:tipo_lista;
begin
   if(L<>nil)then
      if(L^.next<>nil)then
         begin
            pari:=split(L);
            mergesort(L);
            mergesort(pari);
            L:=fondi(L,pari);
         end
end;

{funzioni ausiliarie}
function fun(x:tipo_elemento):tipo_elemento;

begin
   fun:=sqr(x);
end;

function is_pair(x:tipo_elemento):boolean;

begin
   is_pair:=((x mod 2)=0)
end;

{esercizi proposti da Ugo de'Liguoro}
{predicati su liste}
function liste_uguali(L,M:tipo_lista):boolean;

var
   uguali:boolean;
begin
   uguali:=true;
   while((L<>nil)and(M<>nil) and uguali)do
      begin
         uguali:=(L^.element=M^.element);
         L:=L^.next;
         M:=M^.next;
      end;
   liste_uguali:=(uguali and(L=nil)and(M=nil))
end;

function prefix(L,M:tipo_lista):boolean;

var
   uguali:boolean;
begin
   uguali:=true;
   while((L<>nil)and(M<>nil)and(uguali))do
      begin
         uguali:=(L^.element=M^.element);
         L:=L^.next;
         M:=M^.next;
      end;
   prefix:=(uguali and(L=nil))
end;

function sublist(L,M:tipo_lista):boolean;

begin
   if(L=nil)then
      sublist:=true
   else if(L^.element<>M^.element)then
      sublist:=sublist(L,M^.next)
   else
      sublist:=prefix(L,M)
end;

function postfix(L,M:tipo_lista):boolean;

begin
   if((L=nil)and(M=nil))then
      postfix:=true
   else if((L=nil)and(M<>nil))then
      postfix:=false
   else if((L<>nil)and(M=nil))then
      postfix:=false
   else if(L^.element<>M^.element)then
      postfix:=postfix(L,M^.next)
   else
      postfix:=postfix(L^.next,M^.next)
end;

function all_P(L:tipo_lista):boolean;

begin
   if(L=nil)then
      all_P:=true
   else
      all_P:=is_pair(L^.element)and all_P(L^.next)
end;

function exists_P(L:tipo_lista):boolean;

begin
   if(L=nil)then
      exists_P:=false
   else if(is_pair(L^.element))then
      exists_P:=true
   else
      exists_P:=exists_P(L^.next)
end;

{funzioni da liste in liste}
function copia_lista(L:tipo_lista):tipo_lista;

begin
   copia_lista:=L;
end;

function appendi_ric(L,M:tipo_lista):tipo_lista;

begin
   if(L=nil)then
      appendi_ric:=M
   else  if(L^.next=nil)then
      L^.next:=M
   else
      appendi_ric:=appendi_ric(L^.next,M);
   appendi_ric:=L;
end;

procedure appendi_it(var L:tipo_lista;M:tipo_lista);

var
   prec,p:tipo_lista;
begin
   if(L=nil)then
      L:=M
   else
      begin
         p:=L;
         while(p<>nil)do
            begin
               prec:=p;
               p:=p^.next
            end;
         prec^.next:=M;
         p:=prec^.next
      end
end;

procedure inverti_lista(var L:tipo_lista);

var
   M:tipo_lista;
begin
   M:=nil;
   while(L<>nil)do
      begin
         inserisci_in_testa(L^.element,M);
         L:=L^.next
      end;
   L:=M;
end;

function mapfun(L:tipo_lista):tipo_lista;

begin
   if(L=nil)then
      mapfun:=nil
   else
      begin
         L^.element:=fun(L^.element);
         mapfun:=mapfun(L^.next);
         mapfun:=L;
      end
end;

function selectPair(L:tipo_lista):tipo_lista;

var
   tmp:tipo_lista;
begin
   tmp:=nil;
   while(L<>nil)do
      begin
         if is_pair(L^.element)then
            inserisci_in_coda_ric(L^.element,tmp);
         L:=L^.next
      end;
   selectPair:=tmp;
end;

{temi d'esame}

function minore(L,M:tipo_lista):boolean;
{es.1 26.giu.96}
var
   min:boolean;
begin
   min:=true;
   while(L<>nil)and(M<>nil) and min do
      begin
         min:=(L^.element<M^.element);
         L:=L^.next;
         M:=M^.next
      end;
   minore:=min
end;

procedure inserdopo(L:tipo_lista;m,n:tipo_elemento);
{es.3 26.giu.96}
var
   tmp:tipo_lista;
begin
   while(L<>nil)do
      begin
         if(L^.element<>m)then
            L:=L^.next
         else
            begin
               new(tmp);
               tmp^.element:=n;
               tmp^.next:=L^.next;
               L^.next:=tmp;
               L:=tmp^.next
            end
      end
end;

function is_linked_list(L:tipo_lista):boolean;
{es.1 17.dic.96}
begin
   if(L<>nil)then
      begin
         if(L^.next<>nil)then
            if(L^.element<L^.next^.element)then
               is_linked_list:=is_linked_list(L^.next)
            else
               is_linked_list:=false
      end
   else
      is_linked_list:=false
end;

function inverti_it(L:tipo_lista):tipo_lista;
{es.2 16.set.97}
var
   tmp,inv:tipo_lista;
begin
   inv:=nil;
   while(L<>nil)do
      begin
         tmp:=L;
         L:=L^.next;
         tmp^.next:=inv;
         inv:=tmp;
         if((inv^.element mod 2)=0)then
            inv:=insert_head(inv^.element,inv);
      end;
   inverti_it:=tmp;
end;

function inverti_ric(Lst:tipo_lista):tipo_lista;
{es.2 16.set.97}
   procedure inv_aux(L,inv:tipo_lista);
   var
      tmp:tipo_lista;
   begin
      if(L=nil)then
         inverti_ric:=inv
      else
         begin
            tmp:=L^.next;
            L^.next:=inv;
            if((L^.element mod 2)=0)then
               L:=insert_head(L^.element,L);
            inv_aux(tmp,L)
         end
   end;
begin
   inv_aux(Lst,nil)
end;

function immersa(L,M:tipo_lista):boolean;
{es.1 31.mar.98}
begin
   if(L=nil)then
      immersa:=true
   else if(M=nil)then
      immersa:=false
   else
      if(L^.element=M^.element)then
         immersa:=immersa(L^.next,M^.next)
      else
         immersa:=immersa(L,M^.next)
end;


function max_seq(L:tipo_lista;x:tipo_elemento):tipo_lista;
{es.3 16.set.97}
var
   l_max,l_tmp:integer;
   p_max:tipo_lista;
begin
   max_seq:=nil;
   l_max:=0;
   while(L<>nil)do
      begin
         if(L^.element<>x)then
            L:=L^.next
         else
            begin
               p_max:=L;
               l_tmp:=0;
               while(L<>nil)and(L^.element=x)do
                  begin
                     inc(l_tmp);
                     L:=L^.next
                  end;
               if(l_tmp>l_max)then
                  begin
                     l_max:=l_tmp;
                     max_seq:=p_max;
                  end
            end
      end
end;


procedure via_magg_ric(var L:tipo_lista;x:tipo_elemento);
{es.1 15.set.98}
var
   tmp:tipo_lista;
begin
   if(L<>nil)then
      if(L^.element>x)then
         begin
            tmp:=L;
            L:=L^.next;
            dispose(tmp);
            via_magg_ric(L,x)
         end
      else
         via_magg_ric(L^.next,x);
end;

procedure via_magg_it(var L:tipo_lista;x:tipo_elemento);

var
   prec,p:tipo_lista;
begin
   while(L<>nil)and(L^.element>x)do
      begin
         p:=L;
         L:=L^.next;
         dispose(p)
      end;
   p:=l;
   while(p<>nil)do
      begin
         if(p^.element<=x)then
            begin
               prec:=p;
               p:=p^.next
            end
         else
            begin
               prec^.next:=p^.next;
               p:=prec^.next
            end
      end
end;

var
   lista,lista2:tipo_lista;
   vettore:tipo_vettore;

begin
   writeln;
   leggi_lista_da_tastiera(lista);
   stampa_lista(lista);
   writeln('cancella_tutti_it');
   cancella_tutti_it(1,lista);
   stampa_lista(lista);
end.