数据结构必学：反转链表的多种实现方法与图解

2 年 ago

韵, 科

2 minutes

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

反转一个链表

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

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

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

Iterative Approach
Recursive Approach

使用迭代方法反转链表

要迭代地反转一个链表，我们需要存储下一个和前一个元素的引用，这样当我们交换链表中下一个元素的内存地址指针时，它们不会丢失。以下示例演示了我们通过改变引用来反转链表。

以下是反转LinkedList的步骤。创建 3 个实例：current、next、previous。循环以下步骤直到 current 不为 null。

Save the next Node of the current element in the next pointer.
Set the next of the current Node to the previous. This is the MVP line.
Shift previous to current.
Shift the current element to next.

最后，因为目前的指针已经超过了最后一个元素的位置，所以我们需要将头指针设为我们到达的最后一个元素。这个最后一个元素在之前已经被记录下来了。将头指针设置为之前的元素。因此，我们得到了新链表的头指针，即老链表的最后一个元素。

这是一个非常简单的LinkedList实现。请注意，这不是一个适用于生产环境的实现，我们将其保持简单，以便我们的重点仍然放在反转链表的算法上。

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

import com.Olivia.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存储库中查看完整代码和更多的数据结构和算法示例。

#数据结构 #算法 #编程教程 #链表 #链表反转