הפיכת רשימה מקושרת להפוכה

היפוך רשימה מקושרת הוא בעיה מעניינת במבני נתונים ובאלגוריתמים. במדריך זה, אנחנו נדון בשוני האלגוריתמים להפיכת רשימה מקושרת ונממש אותם בעזרת ג'אווה.

הפיכת רשימה מקושרת

LinkedList היא מבנה נתונים המאחסן את הנתונים בדרך לינארית. אף על פי שאינו בדרך רציפה. כל איבר ב-LinkedList מכיל חלק נתונים וכתובת לאיבר הבא ב-LinkedList. האיברים של LinkedList ידועים בשם צמתים.

LinkedList דו כיוונית מאחסנת שתי כתובות. כתובת לאיבר הקודם וכתובת לאיבר הבא.

בכדי להיפך רשימת קישורים במקום, אנו צריכים להיפך את הפוינטרים כך שהאיבר הבא עכשיו מצביע לאיבר הקודם. הנה הקלט והפלט. ראש הרשימה המקושרת הוא הצומת הראשון. אין לאיבר אחר כתובת שמאוחסנת עבור זה. זנב הרשימה המקושרת הוא הצומת האחרון. הכתובת הבאה שמאוחסנת בצומת זה היא null. אנו יכולים להיפך רשימת קישורים כך שהראש והזנב גם ישתנו באמצעות:

• גישה איטרטיבית
• גישה רקורסיבית

גישה איטרטיבית להיפך רשימת קישורים

להיפוך LinkedList בצורה איטרטיבית, אנו צריכים לאחסן את הפניות של האיברים הבאים והקודמים, כך שהם לא יאבדו כאשר אנו מחליפים את כתובות הזיכרון לאיבר הבא בLinkedList. ההדגמה הבאה מדגימה כיצד נהפוך את ה-LinkedList שלנו על ידי שינוי ההפניות.

הליך הבא יש לבצע כדי להיפך את ה-LinkedList. צור 3 מופעים: נוכחי, הבא, קודם. חזור על השלבים הבאים עד שהנוכחי אינו null:

• שמור את האיבר הבא של הנוכחי באיבר הבא.
• הגדר את האיבר הבא של הקודם לאיבר הקודם. זהו השורה החשובה ביותר.
• הזז את הקודם לנוכחי.
• הזז את האיבר הנוכחי לאיבר הבא.

בסיום, מאחר שהנוכחי הלך למקום אחד לפני האיבר האחרון, עלינו להגדיר את הראש לאיבר האחרון שהגענו אליו. זה זמין בקודם. הגדר ראש לקודם. לכן יש לנו את הראש החדש של ה-LinkedList שהוא האיבר האחרון של ה-LinkedList הקודם.

כאן מימוש פשוט מאוד של LinkedList. שים לב שזה אינו מימוש מוכן לייצור ושמרנו על פשטות כדי שהמיקוד שלנו יישאר על אלגוריתם להיפוך הרשימה המקושרת.

package com.journaldev.linkedlist.reverse;

public class MyLinkedList {

	public Node head;

	public static class Node {

		Node next;

		Object data;

		Node(Object data) {
			this.data = data;
			next = null;
		}
	}
}

התוכנית ב-Java להיפך LinkedList בצורה איטרטיבית והדפסת האיברים שלו ניתנת להלן:

package com.journaldev.linkedlist.reverse;

import com.journaldev.linkedlist.reverse.MyLinkedList.Node;

public class ReverseLinkedList {

	public static void main(String[] args) {
		MyLinkedList myLinkedList = new MyLinkedList();
		myLinkedList.head = new Node(1);
		myLinkedList.head.next = new Node(2);
		myLinkedList.head.next.next = new Node(3);

		printLinkedList(myLinkedList);
		reverseLinkedList(myLinkedList);
		printLinkedList(myLinkedList);

	}

	public static void printLinkedList(MyLinkedList linkedList) {
		Node h = linkedList.head;
		while (linkedList.head != null) {
			System.out.print(linkedList.head.data + " ");
			linkedList.head = linkedList.head.next;
		}
		System.out.println();
		linkedList.head = h;
	}

	public static void reverseLinkedList(MyLinkedList linkedList) {
		Node previous = null;
		Node current = linkedList.head;
		Node next;
		while (current != null) {
			next = current.next;
			current.next = previous;
			previous = current;
			current = next;
		}
		linkedList.head = previous;
	}

}

פלט:

1 2 3 
3 2 1 

היפוך רשימת מקושרים באופן רקורסיבי

כדי להפוך את רשימת המקושרים באופן רקורסיבי, עלינו לחלק את רשימת המקושרים לשני חלקים: ראש ושארית. הראש מצביע לאיבר הראשון בתחילה. השארית מצביעה לאיבר הבא מהראש.

אנו עוברים על רשימת המקושרים באופן רקורסיבי עד לאיבר האחרון השני. לאחר שהגענו לאיבר האחרון, אנו מגדירים אותו כראש. משם אנו עושים את הבא: עד שנגיע לתחילת רשימת המקושרים. node.next.next = node; node.next = null; כדי לא לאבד מעקב אחר הראש המקורי, נשמור עותק של מופע הראש.

הנה הדמיה של הליך המופיע לעיל. התוכנית ב-Java להפיכת רשימת המקושרים באופן רקורסיבי היא:

public static Node recursiveReverse(Node head) {
	Node first;

	if (head==null || head.next == null)
		return head;

	first = recursiveReverse(head.next);
	head.next.next = head;
	head.next = null;

	return first;
}

אנו פשוט מעבירים את head.next בקריאה רקורסיבית כדי להגיע לסוף רשימת המקושרים. לאחר שהגענו לסוף, אנו מגדירים את האיבר האחרון השני כהמשך של האיבר האחרון ומגדירים את הפנקס הבא של האיבר האחרון השני ל-NULL. האיבר האחרון יסומן כהראש החדש. השתמש בקוד הבא כדי להפוך את רשימת המקושרים באמצעות הגישה הרקורסיבית.

myLinkedList.head = recursiveReverse(myLinkedList.head);

הפלט יישאר כמו הגישה האיטרטיבית הקודמת.

מורכבות הזמן והמרחב בהיפך של רשימה מקושרת

מורכבות בזמן – O(n) מורכבות במרחב – O(1)

תוכל לבדוק את הקוד המלא ועוד דוגמאות למבני נתונים ואלגוריתמים מהמאגר שלנו ב־GitHub.