/*
 * Implemente versões recursivas das rotinas abaixo.
 */
#include <stdlib.h>
#include <stdio.h>

typedef struct No {
  int v;
  struct No* prox;
} No;

int n_elementos (No* p_n) {
  if (p_n == NULL)
    return 0;
  else
    return 1 + n_elementos(p_n->prox);
}

void libera(No* p_n) {
  if (p_n != NULL) {
    libera(p_n->prox);
    free(p_n);
  }
}

int iguais (No* l1, No* l2) {
  if (l1 == NULL && l2 == NULL)
    return 1;
  if (l1 == NULL || l2 == NULL)
    return 0;
  if (l1->v != l2->v)
    return 0;
  return iguais(l1->prox, l2->prox);
}

No* intercala(No** x, No** y) {
  if (*x == NULL) {
    No* r = *y;
    *y = NULL;
    return r;
  }
  No *z = intercala(y, &(*x)->prox);
  (*x)->prox = z;
  No *r = *x;
  *x = NULL;
  return r;
}

No* intercala2(No* x, No* y) {
  if (x == NULL) 
    return y;
  x->prox = intercala2(y, x->prox);
  return x;
}

void insere_final(No** p_p_n, int v) {
  if (*p_p_n == NULL) {
    No* n = malloc(sizeof(No));
    n->v = v;
    n->prox = NULL;
    *p_p_n = n;
  } 
  else
    insere_final(&(*p_p_n)->prox, v);
}

void imprime(No* p) {
  if (p != NULL) {
    printf("%d\n", p->v);
    imprime(p->prox);
  }
}


No* cria_no(int v) {
  No* n = (No*) malloc(sizeof(No));
  n->v = v;
  return n;
}



No* inverte(No* p) {  
  if (p == NULL || p->prox == NULL)
    return p;
  No *r = inverte(p->prox);
  p->prox->prox = p;
  p->prox = NULL;
  return r;
}


No* concat(No* ap_elem, No* ap_lista) {
  ap_elem->prox = ap_lista;
  return ap_elem;
}

int main() {
  No* x, *y;

  x = concat(cria_no(3), NULL);
  x = concat(cria_no(1), concat(cria_no(2), x));
  printf("X: Numero de elementos: %d\n", n_elementos(x));
  imprime(x);


  /*  y = concat(cria_no(30), NULL); */
  y = concat(cria_no(10), concat(cria_no(20), NULL));
  printf("Y: Numero de elementos: %d\n", n_elementos(y));
  imprime(y);

  imprime(intercala2(x, y));

  return 0;
}