/* constrói uma LL que representa a intercalação de duas LLs dadas; */
/* vamos assumir que as LLs têm cabeça de lista, para facilitar     */
apont intercala1 (apont p, apont q) {
  apont r = malloc(sizeof(*p)), t = r; 
  /* r é o início da LL resultante e t a última célula dessa LL */
  p = p->prox; q = q->prox; 
  while (p != NULL && q != NULL) {
    t->prox = malloc(sizeof(*p)); 
    t = t->prox;
    if (p->chave <= q->chave) {
      t->chave = p->chave;
      p = p->prox; 
    }
    else {
      t->chave = q->chave;
      q = q->prox;
    }
  } 
  if (p == NULL) p = q;
  while (p != NULL) {
    t->prox = malloc(sizeof(*p)); 
    t = t->prox;
    t->chave = p->chave;
    p = p->prox; 
  }
  return r;
}

/* intercala as duas listas, usando suas próprias células */
/* vamos assumir que as LLs têm cabeça de lista, para facilitar     */
void intercala2 (apont p, apont q) {
  apont aux; 
  while (q->prox != NULL) {
    while (p->prox != NULL && p->prox->chave <= q->prox->chave) 
      p = p->prox; 
    aux = q->prox; 
    q->prox = q->prox->prox;
    aux->prox = p->prox; 
    p->prox = aux; 
    p = aux;
  }
  free(q);
}

/* inverte as células de uma LL sem cabeça */ 
apont inverte (apont p) {
  apont ant = NULL, q; 
  while (p != NULL) {
    q = p->prox; 
    p->prox = ant; 
    ant = p; 
    p = q;
  }
  return ant;
}

/* verifica se uma LL sem cabeça está em ordem não decrescente */
int verifica_ordem (apont p) {
  while (p->prox != NULL) {
    if (p->chave > p->prox->chave) 
      return 0;
    p = p->prox;
  }
  return 1;
}