Practice #4
Lektion 13 von 14 im Kurs Linked List - Datenstrukturen-Serie #5 von Coddy.
Aufgabe
EinfachGegeben sind zwei sortierte Ganzzahl-Arrays a und b (die Werte von zwei sortierten verketteten Listen). Schreiben Sie eine Funktion mergeSorted, die ein einzelnes sortiertes Array zurückgibt, das alle Werte aus beiden Eingaben enthält.
Verwenden Sie eine verkettete Liste, um dieses Problem zu lösen! Durchlaufen Sie beide Listen parallel und nehmen Sie wiederholt den kleineren Kopf in Ihr Ergebnis auf.
Sie müssen die Klasse LinkedList verwenden (bereitgestellt in linkedlist.<ext> zusammen mit node.<ext>) — verwenden Sie keine in der Sprache eingebauten Funktionen wie das Umkehren von Arrays, Slicing oder Standardbibliotheks-Listenoperationen, um das Ergebnis zu berechnen.
Probier es selbst
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char line1[8192];
char line2[8192];
if (!fgets(line1, sizeof(line1), stdin)) line1[0] = '\0';
if (!fgets(line2, sizeof(line2), stdin)) line2[0] = '\0';
int a[4096];
int alen = 0;
char* tok = strtok(line1, " \t\r\n");
while (tok) { a[alen++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
int b[4096];
int blen = 0;
tok = strtok(line2, " \t\r\n");
while (tok) { b[blen++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
int rs = 0;
int* r = mergeSorted(a, alen, b, blen, &rs);
for (int idx = 0; idx < rs; idx++) {
if (idx > 0) printf(" ");
printf("%d", r[idx]);
}
printf("\n");
return 0;
}
