Listen verdoppeln

[Andy85]

Hallo alle zusammen,

ich wollte zwei Listen Listen zu einer neuen Liste zusammenführen und diese anschlieschend ausgeben. Die beiden Klassen sehen bis jetzt so aus:

public class Knoten {
	int wert;
	Knoten naechster;
	
	Knoten( int w, Knoten k) {
		this.wert = w;
		this.naechster = k;
	}
}

und die andere Klasse:

public class KnotenTest {

	
	public static void drucke(Knoten listHead){
		while (listHead != null){
			System.out.print(listHead.wert+" ");
			listHead = listHead.naechster;
		}
		System.out.println();
	}
	public static void main(String[] args) {
		Knoten list1 = new Knoten(3, new Knoten(17, new Knoten(8, null)));
		Knoten list2 = new Knoten(99, new Knoten(11, new Knoten(22, null)));
		drucke(list1);
	}
}

Eine grobe Vorstellung der Methode zum Zusammenführen habe ich schon:

	public static void vereine(Knoten listHead1, Knoten listHead2){
   Knoten listTmp
		// Hier könnte eine while-Schleife hin
                ...
   while (listTmp != null){
			System.out.print(listTmp.wert+" ");
			listTmp = listTmp.naechster;
		}
		System.out.println();
      
}

Aber hier hört es schon wieder auf. Habe keine Idee wie ich den Rest implementieren soll. Ein Gedanke wäre, eine neue Liste erzeugen, mit ner while-Schleife prüfen, dass das nächste Element nicht null ist und die Liste(listTmp) mit den Werten der beiden Listen listHead1 und listHead2 zu füllen.
Weiß einer wie ich das anstellen können?
Schon mal danke im vorraus.
MfG

 

[SlaterB]

tja, du könntest eine 'Liste' durchlaufen und als next des letzen Elementes (bisher null) den Kopf der zweiten Liste setzen,
schon sind sie zusammen

----------


eine oder beide Listen zu durchlaufen und deren Werte zum Bau neuer Knoten zu benutzen ginge auch,
wenn du eine oder beide Listen unbeschädigt lassen willst

fange ganz einfach an, erstmal einen Knoten neu zu erstellen mit dem Wert eines anderen,
dann zwei und drei manuell und diese manuell untereinander verknüpfen,
vielleicht siehst du dann das System für die Schleife

 

[Andy85]

Danke für die Idee. Habe das jetzt probiert, sogar mehrmals...
Meine Methode sieht jetzt so aus:

	public static void union(Knoten listHead1, Knoten listHead2){
		while (listHead1.naechster != null){
			listHead1 = listHead1.naechster;
		}
		listHead1.naechster = listHead1;
		if (listHead1.naechster != null)
			listHead1.naechster = listHead2;
		
		while (listHead1 != null){
			System.out.print(listHead1.wert+" ");
			listHead1 = listHead1.naechster;
		}
		System.out.println();
	}

Allerdings noch fehlerhaft, da ich bei den folgenden Listen:

Knoten list1 = new Knoten(3,
					   new Knoten(17,
					   new Knoten(8, null)));
		Knoten list2 = new Knoten(99,
					   new Knoten(11,
				       new Knoten(22, null)));
		drucke(list1);
		union(list1, list2);

Immer diese Ausgabe bekomme:
8, 99, 11, 22

Das mit dranhängen hat immerhin schon geklappt. Aber weiß du wo mein Fehler ist?

 

[SlaterB]

> Immer diese Ausgabe bekomme

in deinem Code-Ausschnitt steht das 'drucke' doch vor dem 'union',
was soll ich dann davon halten?
entweder ist die Ausgabe vor dem Verbinden oder du redest von einer ganz anderen Ausgabe,
poste lieber vollständigen Code, mehr als 50 Zeilen sind das doch bisher nicht

zu union:
in Zeil 2-4 durchläufst du die erste Liste,
so dass am Ende listHead1 das letzte Element von Liste1 ist, garantiert mit naechser == null,
gut

dann kommt die Zeile
> listHead1.naechster = listHead1;
welchen Sinn hat die in deinem Code? warum hast du sie geschrieben?
ich kann da nicht nur keinen Vorteil für die union erkennen,
das ist auch noch sehr gefährlich, jeder weitere Durchlauf der Liste führt zu einer Endlosschleife,
das letzte Element zeigt immer auf sich selber, hat nie 'naechser == null', ein Kreis

die nächse Zeile ist
> if (listHead1.naechster != null)

welchen Sinn hat diese denn? nach dem Code aus Zeile 2-4 war ja sichergestellt,
dass listHead1auf das letzte Element von Liste1 zeigt, garantiert mit naechser == null,
von daher wäre die Abfrage unnötig

außerdem schreibst du ja direkt davor
> listHead1.naechster = listHead1;
also ist die Abfrage doppelt unnötig, listHead1.naechster ist garantiert nicht null sondern listHead1,
weil du es eine Zeile zuvor doch zugewiesen hast!

wenn du solch konfusen Code postest, dann kann ich kaum helfen

 

[Andy85]

Sry für den Unfug. Ich sitze schon zu lange an Listen, muss einiges noch mal von vorne durchgehen. Einfach beliebigen Code ausprobieren bringt nix. Morgen poste ich nochmal den ganzen Code...vielleicht komme ich noch in der Nacht auf eine richtige Lösung :wink: