Μεσαίο Στοιχείο Λίστας [25 Μονάδες]
Γράψτε μια συνάρτηση middle_element η οποία παίρνει ως όρισμα μια λίστα ακεραίων
τύπου List και επιστρέφει μια νέα λίστα με μοναδικό στοιχείο το μεσαίο στοιχείο της λίστας.
Αν ο αριθμός των στοιχείων είναι άρτιος, μπορεί να επιστραφεί οποιοδήποτε από τα μεσαία
στοιχεία. Για παράδειγμα, αν δοθεί η ακόλουθη λίστα:
12 -> 99 -> 42 -> 3 -> 17 -> NULL
περιμένουμε να επιστραφεί η ακόλουθη λίστα:
42 -> NULL
Ποια είναι η χρονική και η χωρική πολυπλοκότητα του αλγορίθμου σας (8/25 της βαθμολογίας);
Ο τύπος List δίνεται παρακάτω:
typedef struct node {
int value;
struct node * next;
} * List;
Bonus: Αν ο αλγόριθμός σας βρίσκει το μεσαίο στοιχείο της λίστας χωρίς να την διατρέξει πάνω από μία φορές.
Η απλή λύση μετρά πρώτα τους κόμβους και μετά ξαναπερπατά ως τη μέση· για το bonus,
σκεφτείτε δύο δείκτες που ξεκινούν μαζί αλλά προχωρούν με διαφορετική ταχύτητα.
Μην ξεχάσετε ότι πρέπει να επιστραφεί νέα λίστα (ένας νέος κόμβος με malloc),
και ελέγξτε τι επιστρέφετε για κενή λίστα ή λίστα ενός στοιχείου.
Αριθμός στον οδηγό: Α21.9
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2025-sep-q4 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2025-sep-q4.html ·
Markdown (GitHub)