מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/רשימות מקושרות/תרגילים/החלפת הסדר של רשימה מקושרת חד כוונית/שאלה

להלן מבנה אפשרי לרשימה מקושרת חד-כוונית.

הרשימה מורכבת מחוליות. כל חוליה נראית כך:

# A data structure that describes a link which has a value, and can
#	be connected to a following and previous link.
Link
	# The next Link.
1	next
	# The value at this link.
2	value

להלן הפסוודו-קוד לרשימה עצמה:

# A data structure that describes a (doubly-linked) list of values.
List
        # The leftmost link.
1      front
        # The size (number of links).
2      size

(שימו לב שזה כמובן אינו המבנה היחידי האפשרי לרשימה מקושרת חד-כוונית: ייתכנו מימושים אחרים בעלי שדות עם שמות ומשמעויות שונים מעט.)

אנא הצע אלגוריתם בסיבוכיות $\displaystyle O(n)$ ובעל דרישת זיכרון קבועה (כלומר, שאינה גדלה עם $\displaystyle n$), ההופכת את סדר הרשימה (האיבר הראשון ייהפוך להיות האיבר האחרון, האיבר השני ייהפוך להיות האיבר לפני אחרון, וכולי).