Practice #2
Lektion 11 von 14 im Kurs Linked List - Datenstrukturen-Serie #5 von Coddy.
Aufgabe
EinfachSchreiben Sie eine Funktion findMiddle, die ein Ganzzahl-Array arr (die Werte einer verketteten Liste) erhält und den mittleren Wert zurückgibt.
Bei ungeraden Längen ist es die exakte Mitte. Bei geraden Längen ist es der zweite der beiden mittleren Knoten (Index length / 2). Wenn die Liste leer ist, geben Sie -1 zurück.
Verwenden Sie eine verkettete Liste, um dieses Problem zu lösen! Der klassische Ansatz sind zwei Pointer: ein langsamer und ein schneller. Wenn der schnelle Pointer das Ende erreicht, befindet sich der langsame in der Mitte.
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 line[8192];
if (!fgets(line, sizeof(line), stdin)) line[0] = '\0';
int arr[4096];
int len = 0;
char* tok = strtok(line, " \t\r\n");
while (tok) { arr[len++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
int r = findMiddle(arr, len);
printf("%d\n", r);
return 0;
}
