Nelle liste ordinate, i casi possibili sono sempre 3:
-inserisci in testa;
-inserisci in mezzo;
-inserisci in coda;
per tutti e tre i casi vanno fatte le prove, se si verificano ad esempio il primo o il secondo, inutile andare al terzo.quindi, prima dell'inserimento all'intero ordinato, fai cosi:

if (p->valore < testa->valore)
//inserisci in testa