反轉鏈表

反转链表是数据结构和算法中一个有趣的问题。在本教程中，我们将讨论各种算法来反转一个链表，并使用Java实现它们。

反转链表

链表是一种以线性方式存储数据的数据结构，尽管不是连续的。每个链表元素包含一个数据部分和指向链表下一个元素的地址。链表元素通常被称为节点。

双向链表存储两个地址，分别是前一个元素的地址和下一个元素的地址。

為了在原地反轉鏈表，我們需要反轉指針，使下一個元素現在指向前一個元素。以下是輸入和輸出。 鏈表的頭是第一個節點。沒有其他元素存儲了此節點的地址。鏈表的尾部是最後一個節點。此節點中存儲的下一個地址為 null。我們可以通過以下方式反轉鏈表，使頭和尾也發生變化：

• 迭代方法
• 遞歸方法

反轉鏈表的迭代方法

為了迭代地反轉 LinkedList，我們需要存儲下一個和前一個元素的引用，這樣當我們交換 LinkedList 中下一個元素的內存地址指針時，它們就不會丟失。以下插圖演示了我們將如何通過改變引用來反轉 LinkedList。

以下是反轉 LinkedList 的步驟。創建 3 個實例：current、next、previous。循環以下直到 current 不為空：

• 保存當前元素的下一個節點到 next 指針中。
• 將當前節點的下一個節點設置為 previous。這是 MVP 行。
• 將 previous 轉移到 current。
• 將當前元素轉移到 next。

最後，因為當前已經超前於最後一個元素一個位置，我們需要將頭部設置為我們到達的最後一個元素。這在 previous 中可用。將頭部設置為 previous。這樣我們就有了 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 程序，用於迭代地反轉鏈表並打印其元素：

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 

以遞歸方式反轉鏈表

要以遞歸方式反轉LinkedList，我們需要將LinkedList分為兩部分：頭部和剩餘部分。頭部最初指向第一個元素。剩餘部分指向從頭部開始的下一個元素。

我們遞歸地遍歷LinkedList，直到倒數第二個元素。一旦我們到達最後一個元素，將其設置為頭部。從那裡開始，直到達到LinkedList的開頭，我們執行以下操作。node.next.next = node;node.next = null;為了不丟失原始頭部的軌跡，我們將保存頭部實例的副本。

以下是上述過程的示例。 以遞歸方式反轉LinkedList的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，以便前往LinkedList的末尾。一旦我們到達末尾，我們將倒數第二個元素設置為最後一個元素的下一個，並將倒數第二個元素的下一個指針設置為NULL。最後一個元素將被標記為新的頭部。使用以下代碼使用遞歸方法反轉鏈表。

myLinkedList.head = recursiveReverse(myLinkedList.head);

輸出將保持與以前的迭代方法相同。

反轉鏈表的時間與空間複雜度

時間複雜度 – O(n) 空間複雜度 – O(1)

您可以從我們的GitHub存儲庫查看完整代碼和更多DS＆算法示例。