Non me n'ero accorta ma c'è un errore di distrazione nel codice precedente!
Comunque grazie per la risposta ramy89..ho corretto il codice in questo modo:
codice:
bool sottolista(list *head1,list *head2){
     if(head1 != NULL && head2 != NULL){
       if(head1->info != head2->info)
        sottolista(head1->next,head2);
     else 
        sottolista(head1->next,head2->next);
     }
     if(head2 == NULL) return true;
     else return false;
}
Il punto è che così la funzione mi ritorna sempre vera, perchè la funzione mi trova sempre (attendendomi all'esempio che ho scritto sopra) che i 3 elementi di head2 sono presenti in head1 anche se non consecutivamente.
Per ovviare a questo problema devo introdurre un altra variabile?