Einfügen von Knoten vor einem bestimmten Knoten in doppelt verketteten Liste

Question

I geschaffen doppelt verknüpfte Liste, wie unten

8 <-> 2 <-> 12 

Ich habe folgende Knoten, bevor der Knoten „2“

Knoten einzufügen einzufügen - (8, 22,23,15)

Der Knoten "8" ist bereits vor dem Knoten "2" vorhanden. In diesem Fall möchte ich den Knoten "8" nicht wieder einfügen. Gibt es eine Möglichkeit zu überprüfen, ob "Knoten zum Einfügen" bereits vor dem Knoten vorhanden ist oder nicht?

Ich mag letzten DLL als 8 <-> 22 <-> 23 <-> 15 <-> 2 <-> 12

Answer 1

Wenn Sie jedoch Serie wiederholen nicht wollen:

Aktuelle Liste:

1 ↔ 2 ↔ 3

Einlegen vor 3: (1, 2, 4)

Ergebnis wollte:

1 ↔ 2 ↔ 4 ↔ 3

Es ist ein wenig komplizierter wird, aber nicht viel.

Erste, prüfen Sie, ob der Knoten vor dem man Sie als Basis verwenden Matches alle Ihre Knoten einzuführen. Start für den letzten (so dass Sie immer die längste Serie wiederholen, und vermeiden Sie es).

Wenn eins mit übereinstimmt, überprüfen Sie, ob der Rest der Serie auch übereinstimmt. Wenn dies der Fall ist, beginne beim nächsten (oder füge keinen hinzu, wenn es der letzte ist); Wenn nicht, gehen Sie zurück zu Zuerst Schritt.

zweite und letzte Nachdem Sie den nächsten Knoten ausgewählt haben (wenn Sie nicht auf Erste brachte, starten Sie einfach auf dem ersten) sie nur hinzufügen, bevor der Basis.

Dies ist Pseudo-Code, da ich weiß, Ihre genaue Umsetzung nicht:

Betrachtet:

int[] toAdd = {1, 2, 4}; 

Zum Beispiel können Sie Rekursivität verwenden:

main { 
    int from = 0; 
    for (int i = toAdd.length - 1; i >= 0; i--) { 
     if (checkSerie(toAdd, i, base) { 
      from = i; 
      break; 
     } 
    } 

    // And add: 
    for (int i = from; i < toAdd.length; i++) { 
     addBefore(3, toAdd[i]); // Your add method. 
    } 
} 

private boolean checkSerie (int[] toAdd, int index, Node base){ 
    Node prev = base.prev; 
    if (index < 0) { 
     return true; 
    } 

    if (toAdd[index] != prev) { 
     return false; 
    } 

    return checkSeriei (toAdd, index - 1, prev); 
} 

Hinweis : Ich habe das nicht getestet, es könnte fehlerhaft sein (vielleicht ein bisschen falsch -1 oder sowas), aber sollte genug sein, um dir zu helfen, die Idee zu bekommen.