Αντιστροφή Λίστας [25 Μονάδες]
Γράψτε μια συνάρτηση reverse_list η οποία παίρνει ως όρισμα μια λίστα ακεραίων
τύπου List και επιστρέφει μια νέα λίστα με τους κόμβους της σε αντίστροφη σειρά σε
σχέση με την αρχική. Για παράδειγμα, αν δοθεί η ακόλουθη λίστα:
[12|•]──>[99|•]──>[37|•]──>NULL
περιμένουμε να επιστραφεί η ανεστραμμένη χωρίς παρενέργειες (side-effects) στην αρχική:
[37|•]──>[99|•]──>[12|•]──>NULL
Ποια είναι η χρονική και η χωρική πολυπλοκότητα του αλγορίθμου σας (8/25 της
βαθμολογίας); Ο τύπος List δίνεται παρακάτω:
typedef struct node {
int value;
struct node * next;
} * List;
«Χωρίς παρενέργειες» σημαίνει ότι δεν πειράζετε τους δείκτες next της αρχικής
λίστας: χρειάζεστε νέους κόμβους με malloc. Παρατηρήστε ότι αν διατρέξετε την αρχική
λίστα από την αρχή και εισάγετε κάθε αντίγραφο στην αρχή της νέας, η σειρά βγαίνει
αντεστραμμένη. Σκεφτείτε την κενή λίστα και τι γίνεται αν αποτύχει η malloc.
Αριθμός στον οδηγό: Α21.8
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2024-sep-q5 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2024-sep-q5.html ·
Markdown (GitHub)