Practice #2
Leçon 11 sur 14 du cours Liste chaînée - Série Structures de données n°5 de Coddy.
Défi
FacileÉcrivez une fonction findMiddle qui reçoit un tableau d'entiers arr (les valeurs d'une liste chaînée) et retourne la valeur du milieu.
Pour les longueurs impaires, le milieu exact. Pour les longueurs paires, le deuxième des deux nœuds du milieu (index length / 2). Si la liste est vide, retournez -1.
Utilisez une liste chaînée pour résoudre ce problème ! L'approche classique consiste à utiliser deux pointeurs : un lent et un rapide. Lorsque le pointeur rapide atteint la fin, le lent se trouve au milieu.
Vous devez utiliser la classe LinkedList (fournie dans linkedlist.<ext> ainsi que node.<ext>) — n'utilisez pas les fonctions intégrées du langage comme l'inversion de tableaux, le découpage (slicing) ou les opérations de liste de la bibliothèque standard (stdlib) pour calculer le résultat.
Essayez vous-même
#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;
}
