 #include <stdio.h>
 #include <stdlib.h>
 #include <time.h>

struct lista {
     int info;
     struct lista* prox;
};

typedef struct lista Lista;

Lista* lst_insere (Lista* lst, int val){
    Lista* lista = (Lista*)malloc(sizeof(Lista));
    lista -> info = val;
    lista -> prox = NULL;

    if(lst == NULL)
        return lista;

    Lista* aux = lst;
    while(aux->prox != NULL){
        aux = aux->prox;
    }
    aux->prox = lista;
    return lst;
}

Lista* intercala(Lista* l1, Lista* l2){
     Lista* novaLista=NULL;

     Lista* aux1 = l1;
     Lista* aux2 = l2;

  while(aux1!= NULL && aux2 != NULL){
  	novaLista = lst_insere(novaLista, aux1 -> info);
  	novaLista = lst_insere(novaLista, aux2 -> info);


    	 aux1 = aux1->prox;


  		aux2 = aux2->prox;

  }

  Lista* aux3 = novaLista;

  while(aux3 -> prox != NULL){
  	aux3 = aux3 -> prox;
  }

  if(aux1 != NULL){
  	aux3 -> prox = aux1;
  }
  else if(aux2 != NULL){
  	aux3 -> prox = aux2;
  }
  return novaLista;
}

void printa(Lista* lista){

    Lista* aux = lista;
    while(aux != NULL){
        printf("%d ", aux->info);
        aux = aux->prox;
    }
    printf("\n");
}

int main(void){

int i;
    srand(time(NULL));

    Lista* l1 = NULL;
    Lista* l2 = NULL;

    for( i = 0; i < 10; i++){
        l1 = lst_insere(l1, rand() % 100);
        l2 = lst_insere(l2, rand() % 100);
    }

    printa(l1);
    printa(l2);

    Lista* intercalada = intercala(l1, l2);

    printa(intercalada);

}
