反转链接列表

在本教程中,我们将讨论不同的算法来扭转一个 [链接列表]( / 社区 / 教程 /java-linkedlist-linkedlist-java),然后使用Java实现它们。

反转链接列表

链接列表是一个数据结构,以线性的方式存储数据,但不是连续的方式。链接列表的每个元素都包含数据部分和链接列表的下一个元素的地址。

双链接列表存储两个地址. 前一个元素和下一个元素的地址。

In order to reverse a LinkedList in place, we need to reverse the pointers such that the next element now points to the previous element. Following is the input and output. [caption id="attachment_23038" align="aligncenter" width="333"] Input[/caption] [caption id="attachment_23039" align="aligncenter" width="327"] Output[/caption] The head of the LinkedList is the first node. No other element has the address stored for this. The tail of the LinkedList is the last node. The next address stored in this node is null. We can reverse a LinkedList such that the head and tail also get changed using:

迭代方法
回归方法

迭代方法来扭转链接列表

To reverse a LinkedList iteratively, we need to store the references of the next and previous elements, so that they don't get lost when we swap the memory address pointers to the next element in the LinkedList. Following illustration demonstrates how we will reverse our LinkedList by changing the references.

以下是要遵循的步骤来扭转LinkedList。创建3个实例:当前、下一个、以前的。

将当前元素的下一个节点保存到下一个指针中
将当前节点的下一个节点设置为前面。

最后,由于电流比最后一个元素先行了一点,我们需要将头设置为我们达到的最后一个元素。

请注意,这不是一个生产准备的实现,我们一直保持简单,以便我们专注于扭转链接列表的算法。

 1package com.journaldev.linkedlist.reverse;
 2
 3public class MyLinkedList {
 4
 5    public Node head;
 6
 7    public static class Node {
 8
 9    	Node next;
10
11    	Object data;
12
13    	Node(Object data) {
14    		this.data = data;
15    		next = null;
16    	}
17    }
18}

返回链接列表并重复打印其元素的Java程序如下:

 1package com.journaldev.linkedlist.reverse;
 2
 3import com.journaldev.linkedlist.reverse.MyLinkedList.Node;
 4
 5public class ReverseLinkedList {
 6
 7    public static void main(String[] args) {
 8    	MyLinkedList myLinkedList = new MyLinkedList();
 9    	myLinkedList.head = new Node(1);
10    	myLinkedList.head.next = new Node(2);
11    	myLinkedList.head.next.next = new Node(3);
12
13    	printLinkedList(myLinkedList);
14    	reverseLinkedList(myLinkedList);
15    	printLinkedList(myLinkedList);
16
17    }
18
19    public static void printLinkedList(MyLinkedList linkedList) {
20    	Node h = linkedList.head;
21    	while (linkedList.head != null) {
22    		System.out.print(linkedList.head.data + " ");
23    		linkedList.head = linkedList.head.next;
24    	}
25    	System.out.println();
26    	linkedList.head = h;
27    }
28
29    public static void reverseLinkedList(MyLinkedList linkedList) {
30    	Node previous = null;
31    	Node current = linkedList.head;
32    	Node next;
33    	while (current != null) {
34    		next = current.next;
35    		current.next = previous;
36    		previous = current;
37    		current = next;
38    	}
39    	linkedList.head = previous;
40    }
41
42}

输出:

11 2 3 
23 2 1

重复反转链接列表

要反转LinkedList,我们需要将LinkedList分为两部分:头部和剩余部分,头部指向最初的元素,剩余元素指向头部的下一个元素。

一旦我们达到最后一个元素设置为头,从那里我们做以下操作,直到我们到达LinkedList的开始。 node.next.next =节点; node.next = null; **为了不失去原始头的痕迹,我们将保存头实例的副本。

Following is the illustration of the above procedure. The Java program to reverse a LinkedList recursively is:

 1public static Node recursiveReverse(Node head) {
 2    Node first;
 3
 4    if (head==null || head.next == null)
 5    	return head;
 6
 7    first = recursiveReverse(head.next);
 8    head.next.next = head;
 9    head.next = null;
10
11    return first;
12}

我们只需在复发呼叫中传输 head.next 才能进入LinkedList的末尾。一旦我们到达终点,我们将第二个最后一个元素设置为最后一个元素的下一个元素,并将第二个最后一个元素的下一个指针设置为 NULL. 最后一个元素将被标记为新头。

1myLinkedList.head = recursiveReverse(myLinkedList.head);

输出将继续作为以前的迭代方法。

重定向链接列表的空间时间复杂性

时间复杂性 - O(n)空间复杂性 - O(1)

您可以从我们的 GitHub 存储库中查阅完整的代码和更多 DS 和算法示例。