Erlaube Duplikate in Merge sort in der einfach verlinkten Liste C ++ - C ++, Duplikate, Mergesort, Single-Linked-List

Ich ärgere mich jetzt sehr darüber. Ich lerne Merge Sort für Universität und mache das durch Zusammenführen, sortieren Ich habe im Netz gefunden. Allerdings bekomme ich scheinbar KEINE Duplikate und ich möchte Duplikate. Es ist dieses Bit wie folgt, aber ich habe das Bit und das Zeug kommentiert und die Sortierung funktioniert nicht richtig. Gibt es eine Möglichkeit, die Duplikate zu behalten? Vielen Dank

else
{
// Both are equal.
// Arbitraritly chose to add one of them and make
// sure you skip both!


if(c == NULL)
{
c = a;
}
else
{
c->next = a;
c = c->next;
}

a = a->next;
b = b->next;
}

Antworten:

Ich denke, der Hinweis liegt im Kommentar im Code: "Stellen Sie sicher, dass Sie beide überspringen". Durch Inkrementieren beide Listenzeiger hinzufügen, fügen Sie der Ausgabe ein Element hinzu, überspringen jedoch zwei Eingabeelemente. Also nur einen Zeiger inkrementieren. Das andere Element wird dann bei der nächsten Iteration in die Ausgabeliste verschoben.

Wenn Sie die Duplikate behalten möchten, fügen Sie beide zur verknüpften Liste hinzu c. Im Moment hängen Sie nur eine an (d. H. a oder b) an die verknüpfte Liste.

Ändern Sie also Ihren Code so, dass er so aussieht:

temp_a_next = a->next;
temp_b_next = b->next;

if(c == NULL)
{
c = a;
c->next = b;
c = b;
}
else
{
c->next = a;
c = a;
c->next = b;
c = b;
}

a = temp_a_next;
b = temp_b_next;

Noch eine Anmerkung: Der letzte Kopf der sortierten Liste mit Duplikaten hat seinen Startpunkt in a, da bis zum Ende dieses Algorithmus c wird auf das Ende der Liste zeigen, und dieser Algorithmus ändert tatsächlich die Zeiger von a und b Knoten (d. h. c ist keine neue verknüpfte Liste mit neuen Knoten).

Sie können den dritten Fall (den aktuellen else-Block, der im Code aufgeführt ist) beseitigen und den zweiten Fall von ändern a > b zu else- es wird jetzt jeden Fall behandeln, wo a >= bund wird immer platzieren a zuerst in der sortierten Liste.