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

פסוודו-קוד והסבר

להלן הפסוודו-קוד לפתרון:

#Takes a singly-linked list (l) and reverses it.
Reverse(l)
1	new-front = Nil
	
2	while l.front != Nil
3		nxt = l.front.next
4		l.front.next = new-front
5		new-front = l.front
6		l.front = nxt
		
7	l.front = new-front

נתבונן ברשימה המקושרת בתרשים הבא.

• שורה 1 מייצרת מצביע new-front המצביע לNil ‏(A)‏. מצביע זה יצביע לרשימות החוליות שכבר הפכו את סדרן.
• כעת נעבור בלולאה 2-6, כל עוד נותרו איברים אליהם מצביע l.front. בכל איטרציה:
  • שורה 3 מייצרת מצביע nxt המצביע לl.front.next ‏(B)‏.
  • שורה 4 גורמת לl.front.next להצביע לרשימת החוליות שאליה מצביע new-front ‏(C)‏ (בתחילה זו רשימת חוליות ריקה, כמובן).
  • שורה 5 גורמת לnew-front להצביע לl.front ‏(D)‏
  • שורה 6 מקדמת את l.front לחוליה הבאה (E).
  • כלומר, כל איטרציה מעבירה חוליה מתחילת הרשימה לראש רשימת חוליות אליה מצביע new-front‏.‏ (F) מראה זאת בצורה ברורה יותר עבור האיטרציה הראשונה.
• לאחר סיום הלולאה, שורה 7 עושה את כל מה שנותר: לגרום לl.front להצביע לחוליה הראשונה בnew-front.

100%

ניתוח סיבוכיות וזיכרון

קל לראות שהסיבוכיות היא $\displaystyle \Theta (n)$:

1. 1 ו7 הן $\displaystyle O(1)$.
2. 3-6 הן $\displaystyle O(1)$ ולכן 2-6 $\displaystyle \Theta (n)$ (כי ברור שהלולאה מתבצעת $\displaystyle n$ פעמים).

כמו כן השתמשנו בכמות מוגבלת של זכרון (השתמשנו בשני משתני עזר בלבד).