Γράψτε ένα αλγόριθμο ο οποίος διαγράφει την μεσαία τιμή ενός Single Linked List, δεδομένου ότι το μέγεθος του Linked List σας είναι άγνωστο, και δικαιούστε να επισκεφθείτε το Linked List μόνο μια φορά. (με ένα βρόχο)
Στην αρχή ίσως να φαίνεται δύσκολο, αλλά είναι αρκετά εύκολο αν έχεις εμπειρία με τέτοια προβλήματα. Το μυστικό για την λύση αυτού του προβλήματος είναι το Runner Technique.
Η λογική είναι ότι κάνουμε iterate σε ένα Linked List με δυο δείκτες την ίδια ώρα, με τον ένα να είναι μπροστά από τον άλλο και ο "γλήγορος" δείκτης, είναι μπροστά με μια σταθερή τιμή. Η τεχνική αυτή είναι αρκετά χρήσιμη όταν δεν ξέρουμε το μέγεθος του Linked List, και θέλουμε να φτάσουμε το μεσαίο στοιχείο. Όταν ο "γλήγορος" δείκτης φτάσει το τέλος, (και είναι x2) τότε ο "αργός" δείκτης θα είναι στην μέση.
Άρα μόλις φτάσουμε στο μεσαίο στοιχείο, με τον αργό δείκτη έχουμε ακόμη μία δυσκολία. Δεν μπορούμε να ταξιδέψουμε πίσω αφού είναι single-linked list και άρα δεν μπορούμε να αλλάξουμε τον δείκτη του προηγούμενου στον επόμενο για να διαγράψουμε την μεσαία τιμή. Άρα τι κάνουμε;
Σκεφτείτε το λίγο μόνοι σας και μετά δείτε την απάντηση μου.
Μια έξυπνη λύση, και όπως το σκεφτούμε εγώ (αλήθεια δεν μπορώ να σκεφτώ κάτι άλλο, όποιος έχει δεύτερη λύση να την ποστάρει) είναι να ανταλλάξω την τιμή του επόμενου node (μπροστά από το middle node) με το middle node και να διαγράψω το επόμενο node που τώρα θα έχει την τιμή του μεσαίου node.
Και ένα diagram που υλοποιεί την λύση του προβλήματος.
Με thumbnail δεν φαίνονται τα γράμματα.
Δεν έχω γράψει τον αλγόριθμό ακόμη, είναι σε ψευδο-κώδικα, ίσως επιστρέψω πίσω με μια απάντηση σε Python, όποιος θέλει ας το δοκιμάσει.