תרגול #2

שיעור 11 מתוך 14 בקורס רשימה מקושרת – סדרת מבני נתונים #5 של Coddy.

אתגר

קל

כתבו פונקציה findMiddle שמקבלת מערך של מספרים שלמים arr (הערכים של רשימה מקושרת) ומחזירה את הערך האמצעי.

באורך אי־זוגי, את הערך האמצעי המדויק. באורך זוגי, את השני מבין שני הצמתים האמצעיים (האינדקס length / 2). אם הרשימה ריקה, החזירו -1.

השתמשו ברשימה מקושרת כדי לפתור את הבעיה! הגישה הקלאסית היא להשתמש בשני מצביעים: אחד איטי ואחד מהיר. כשהמצביע המהיר מגיע לסוף, המצביע האיטי נמצא באמצע.

חובה להשתמש במחלקה LinkedList (שמסופקת בקובץ linkedlist.<ext> יחד עם node.<ext>) — אל תשתמשו בפונקציות מובנות של השפה, כמו הפיכת מערכים, חיתוך שלהם או פעולות ספריית התקן על רשימות, כדי לחשב את התוצאה.

נסו בעצמכם

#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;
}