Potresti provare a modificare il caso base così:

codice:
    if ((head1==NULL) && (head2==NULL)){
        delete head3;
        head3 = NULL;
        return;
    }
cioè in pratica deallochi ciò che allochi prima della chiamata ricorsiva e di cui poi non ti servi. Questo ovviamente sempre se ho capito bene come opera la funzione... quindi tu che ne conosci sicuramente meglio la logica controlla se può andare bene (ma mi sembra di sì comunque...)

In ogni caso, visto che la tua è una void function, ti consiglio di evitare scritture tipo

codice:
return polinomiosomma(head1->link,head2,head3->link);
perché equivale a dire: "restituisci alla funzione chiamante il valore restituito da polinomiosomma chiamato con questi argomenti"... ma polinomiosomma, essendo dichiarato come void function (cioè come procedura) non restituirà mai nulla...
Ti basta semplicemente scrivere

codice:
polinomiosomma(head1->link,head2,head3->link);
in maniera tale da attivare ricorsivamente la funzione ma senza restituzioni di valori (che non esistono!)