Bester möglicher Algorithmus, um zu prüfen, ob zwei verknüpfte Listen an einem beliebigen Punkt zusammengeführt werden? Wenn ja, wo?

Question

Mögliches Duplikat:
Verknüpfte Liste Interview Frage

Dies ist eine Interviewfrage, auf die ich keine Antwort habe. Gegeben sind zwei Listen, Sie können die Liste nicht ändern und Sie kennen die Länge nicht. Geben Sie den bestmöglichen Algorithmus an:

1. Prüfen, ob zwei Listen an irgendeiner Stelle zusammengeführt werden?
2. Wenn sie fusionieren, an welchem Punkt werden sie fusionieren?
3. Wenn ich Ihnen erlaube, die Liste zu ändern, wie würden Sie Ihren Algorithmus ändern?

Answer 1

Ich gehe davon aus, dass es sich um einfache verknüpfte Listen handelt und wir sicher eine Hash-Tabelle mit den Zeigern der Listenelemente erstellen können.

Q1: Iterieren Sie bis zum Ende der beiden Listen. Wenn die jeweiligen letzten Elemente gleich sind, verschmelzen die Listen irgendwann.

Komplexität - O(N) , Raumkomplexität - O(1)

Q2:

1. Alle Elemente einer Liste in eine Hashtabelle eintragen
2. Iterieren Sie über Liste 2 und durchsuchen Sie die Hash-Tabelle für jedes Element der Liste. Der erste Treffer (falls vorhanden) ist der Zusammenführungspunkt, und wir haben die Position in der Liste 2.
3. Um die Position in der ersten Liste zu ermitteln, wird die erste Liste erneut durchlaufen und nach dem im vorherigen Schritt gefundenen Element gesucht.

Zeitliche Komplexität - O(N) . Raumkomplexität - . O(N)

Q3:

1. Wie Q1, aber auch die Richtung der Listenzeiger umkehren.
2. Dann werden die umgekehrten Listen durchlaufen, um das letzte gemeinsame Element zu finden - das ist der Verschmelzungspunkt - und die ursprüngliche Reihenfolge der Liste wiederherzustellen.

Zeitliche Komplexität - O(N) . Raumkomplexität - O(1)

Answer 2

Nummer 1: Einfach beide iterieren und dann prüfen, ob sie mit demselben Element enden. Das ist O(n) und kann nicht übertroffen werden (da es möglicherweise das letzte gemeinsame Element ist und der Weg dorthin immer O(n) dauert).

Answer 3

1. Gehen Sie diese beiden Listen parallel um ein Element durch, fügen Sie jedes Element zur Menge der besuchten Knoten hinzu (kann eine Hash-Map oder eine einfache Menge sein, Sie müssen nur prüfen, ob Sie diesen Knoten bereits besucht haben). Bei jedem Schritt prüfen, ob Sie diesen Knoten besucht haben (wenn ja, dann ist es ein Zusammenführungspunkt), und ihn zur Menge der Knoten hinzufügen, wenn Sie ihn zum ersten Mal besucht haben. Eine andere Version (wie von @reinier beschrieben) besteht darin, nur die erste Liste zu durchlaufen, ihre Knoten in der Menge zu speichern und dann nur die zweite Liste mit dieser Menge zu vergleichen. Der erste Ansatz ist schneller, wenn die Listen früh zusammengeführt werden, da man nicht alle Knoten der ersten Liste speichern muss. Der zweite Ansatz ist im schlimmsten Fall besser, wenn beide Listen gar nicht verschmelzen, da die Knoten der zweiten Liste nicht in Set gespeichert wurden.
2. siehe 1.
3. Anstelle von Set können Sie auch versuchen, jeden Knoten zu markieren, aber wenn Sie die Struktur nicht ändern können, ist das nicht so hilfreich. Sie könnten auch versuchen, jeden besuchten Knoten zu entkoppeln und ihn mit einem Schutzknoten zu verknüpfen (den Sie bei jedem Schritt überprüfen, wenn Sie beim Durchlaufen auf ihn gestoßen sind). Das spart Speicher für Set, wenn die Liste lang genug ist.

Answer 4

Durchlaufen Sie sowohl die Liste als auch eine globale Variable zur Ermittlung der Anzahl der NULL begegnet. Wenn sie irgendwann fusionieren, gibt es nur noch 1 NULL sonst gibt es zwei NULL .