Erstellen Sie eine verkettete Liste von zerbrochenen sequcece

Question

Angenommen, wir haben einige Sequenz wie A-> B, C-> D, B-> C, D-> E Wir müssen eine verkettete Liste daraus erstellen. Ausgang: A-> B-> C-> D-> E

Es kann zwei Szenarien geben. Erster Fall, wir haben alle Sequenzen. Im zweiten Fall kommen Sequenzdaten als Stream herein.

Benötigen Sie Hilfe bei der Lösung dieses Problems.

Answer 1

Ich glaube, ich würde die Daten nur speichern, in einer Karte, etwa so:

Map<String, String> sequences = new HashMap<>(); 
String input = "A->B"; 
String[] parts = input.split("->"); // Split input in two parts 

sequences.put(parts[0], parts[1]); 

Diese Karte wird schließlich wie folgt aussehen:

A: B 
B: C 
C: D 
D: E 

und möglicherweise eine zweite unabhängige Kette:

G: F 
H: G 

Jetzt müssen wir finden, wo jede Kette beginnt. Ein Kettenstart kann in dieser Map gefunden werden, indem nach Schlüsseln gesucht wird, die niemals als Wert verwendet werden.

Dies kann tun getan werden:

// make a copy of all keys 
Set<String> chainStarters = new HashSet<>(sequences.keySet()); 

// remove all keys that are also used as a value 
chainStarters.removeAll(sequences.values()); 

Jetzt jeder Kette chainStarters enthält den Start. In dem oben beschriebenen Fall wäre das A und H.

Jetzt müssen Sie nur noch jeden Wert in der sequences Karte nachsehen, beginnend mit den Schlüsseln in chainStarters und einen String daraus machen. Etwas wie:

String currentKey = startKey; // 'A' for example 
StringBuilder sb = new StringBuider(startKey); 

while(sequences.containsKey(currentKey)) { 
    currentKey = sequences.get(currentKey); 

    sb.append("->").append(currentKey); 
} 

System.out.println(sb.toString());