Mi funziona però Se in una lista ho 7 8 e nell'altra ho 4 5 mi ridà la lista con 8->4->-5 sicuramente sbaglio  f = &(*f)->next; qui forse dovrei usare un altra lista di appoggio?? scusate se non mi sono spiegato bene

Il merge di due strutture dati già ordinate - diciamo di dimensioni rispettivamente d₁ e d₂, con d₁+d₂=n  fornisce in output, generalmente in tempo O(n), una struttura dati a sua volta ordinata che contiene tutti e soli gli n dati già contenuti nelle strutture di input. Tale prestazione non è in alcun modo ottenibile con metodi differiti, i.e. join + sort, che ovviamente richiede O(nlogn) passi nel caso migliore.

Nel tipico algoritmo di merging, restando al semplice caso con due strutture in input e con un banale paragone meccanico, il "collettore" di input ossia il canale dal quale viene "prelevato" il prossimo elemento della struttura di output è gestito da una variabile logica, a sua volta generata dal confronto tra i-esimo elemento della struttura (lista, stack, array...) A e j-esimo della struttura B, con i e j opportuni indici indipendenti. Nel caso di strutture dati grezze e primitive come le LLS, agli indici si sostituiranno i due usuali puntatori ausiliari.

Il caso a liste multiple richiede algoritmi meno ingenui, che con k liste di lunghezza media n/k (in altri termini, la lista di output contiene ancora n elementi) possono comunque raggiungere prestazioni dell'ordine di O(nlogk) - un risultato chiaramente derivabile, ad esempio, dall'uso di classici algoritmi per la gestione di uno heap con k nodi, con tempo di push/pop pari appunto a O(logk).


Se invece si parla di una banale operazione append tra due liste, indipendentemente dall'ordinamento, dovrà chiarirlo l'OP.