反转链表

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

反转链表

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

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

为了原地反转链表，我们需要反转指针，使得下一个元素现在指向前一个元素。以下是输入和输出。 链表的头是第一个节点。没有其他元素存储了这个的地址。链表的尾是最后一个节点。存储在这个节点中的下一个地址是 null。我们可以通过以下方式反转链表，使得头和尾也发生变化：

• 迭代方法
• 递归方法

反转链表的迭代方法

将LinkedList迭代地反转，我们需要存储下一个和前一个元素的引用，以防在交换LinkedList中的内存地址指针时它们丢失。以下插图演示了通过更改引用来反转LinkedList的过程。

以下是反转LinkedList所需遵循的步骤。创建3个实例：current（当前）、next（下一个）、previous（前一个）。循环以下步骤，直到current非空：

• 将当前元素的下一个节点保存在next指针中。
• 将current节点的下一个设置为previous。这是最重要的一行。
• 将previous移到current。
• 将当前元素移到next。

最后，由于current已经超过了最后一个元素，我们需要将头部设置为我们达到的最后一个元素。这在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;
		}
	}
}

下面是迭代反转LinkedList并打印其元素的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 

递归反转链表

要递归地反转一个链表，我们需要将链表分为两部分：头部和剩余部分。头部最初指向第一个元素。剩余部分指向头部的下一个元素。

我们递归地遍历链表，直到倒数第二个元素。一旦我们到达最后一个元素，将其设置为头部。然后我们执行以下操作，直到达到链表的起始位置。 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存储库查看完整的代码和更多数据结构与算法示例。