反向链接列表-IGI

时间：2020-02-23 14:41:43 　来源:igfitidea点击:

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

反向链接列表

LinkedList是一种数据结构，它以线性方式存储数据。
虽然不是连续的。

LinkedList的每个元素都包含一个数据部分和LinkedList的下一个元素的地址。

LinkedList元素通常称为节点。

双向LinkedList存储两个地址。
前一个元素和下一个元素的地址。

为了使LinkedList反向，我们需要反向指针，以便下一个元素现在指向上一个元素。

LinkedList的头是第一个节点。
没有其他元素为此存储地址。

LinkedList的尾部是最后一个节点。
存储在该节点中的下一个地址为" null"。

我们可以反转LinkedList，使头部和尾部也可以使用以下方式更改：

迭代法
递归方法

反向链接列表的迭代方法

要迭代地反转LinkedList，我们需要存储下一个和上一个元素的引用，以便在将内存地址指针交换到LinkedList中的下一个元素时，它们不会丢失。

下图说明了如何通过更改引用来反转LinkedList。

以下是反向链接LinkedList的步骤。

创建3个实例：当前，下一个，上一个。

循环以下，直到current不为空：

将当前元素的下一个节点保存在下一个指针中。
将"当前"节点的下一个设置为"上一个"。
这是MVP行。
从上一个移到当前。
将当前元素移至下一个。

最后，由于电流已经比最后一个元素提前一个位置，因此我们需要将head设置为到达的最后一个元素。
这是以前可用的。
前往上一个。
因此，我们有了LinkedList的新头，它是旧LinkedList的最后一个元素。

这是LinkedList的非常简单的实现。
请注意，这不是可用于生产的实现，因此我们将其保持简单，因此我们将重点放在反转链表的算法上。

package com.theitroad.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.theitroad.linkedlist.reverse;

import com.theitroad.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分为两部分：头部分和剩余部分。
Head最初指向第一个元素。
其余部分指向头部的下一个元素。

我们以递归方式遍历LinkedList，直到倒数第二个元素为止。
到达最后一个元素后，将其设置为头。
从那里开始执行以下操作，直到到达LinkedList的开始。

node.next.next =节点; 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)

反向链接列表