Mehrfachvorkommen von Elementen vermeiden, bei der Zusammenfügung zweier Listen

Hi!

Ich möchte zwei Listen zusammenfügen, möchte jedoch Mehrfachvorkommen von Elementen vermeiden. Wie könnte man das denn implementieren?

Hab hier mal den C- Code fürs zusammenfügen. IsEmpty prüft einfach auf Leerheit der jeweiligen Listen.


listptr Union (listptr L1,listptr L2)

{ if ( IsEmpty (*L2)) return L1;
if ( Is Empty (*L1)) return L2;
L1->last->next = L2->first;
L1->last = L->last;
return L1;
}

Am einfachsten geht das, wenn die beiden Listen nach dem selben Kriterium sortiert sind.
Dann kannst du parallel beide Listen durch gehen und Element aus der einen Liste in die andere Einfügen, so lange das Sortierkriterium erfüllt ist.

Ciao,
_

Zitat:

---

Zitat von anda_skoa

Am einfachsten geht das, wenn die beiden Listen nach dem selben Kriterium sortiert sind.
Dann kannst du parallel beide Listen durch gehen und Element aus der einen Liste in die andere Einfügen, so lange das Sortierkriterium erfüllt ist.

Ciao,
_

---

genau, wenn sie nicht sortiert sind, der naive ansatz:
liste zwei durchiterieren und jeweils überprüfen ob das element
in l1 schon vorkommt, wenn nicht an l1 anhängen.
effektiv ist das, aber nicht effizient.