Practice #2
الدرس 11 من 14 في دورة القائمة المرتبطة - سلسلة هياكل البيانات #5 على Coddy.
التحدي
سهلاكتب دالة findMiddle تستقبل مصفوفة من الأعداد الصحيحة arr (قيم قائمة مرتبطة) وتُرجع القيمة الوسطى.
بالنسبة للأطوال الفردية، القيمة الوسطى بالضبط. بالنسبة للأطوال الزوجية، العقدة الثانية من العقدتين الوسطيين (الفهرس length / 2). إذا كانت القائمة فارغة، أرجع -1.
استخدم قائمة مرتبطة (linked list) لحل هذه المشكلة! النهج الكلاسيكي هو استخدام مؤشرين: مؤشر بطيء ومؤشر سريع. عندما يصل المؤشر السريع إلى النهاية، يكون المؤشر البطيء في المنتصف.
يجب عليك استخدام فئة LinkedList (المتوفرة في linkedlist.<ext> مع node.<ext>) — لا تستخدم الأدوات المدمجة في اللغة مثل عكس المصفوفات المدمج، أو الاقتطاع (slicing)، أو عمليات القوائم في المكتبة القياسية (stdlib) لحساب النتيجة.
جرّب بنفسك
#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;
}
