如何在 Java 中反转链表

在本节中，我们将讨论如何在 Java 中反转链表。反转链表是面试中最常问的主题之一。任务是反转一个链表，给定链表的头节点或第一个节点。

给定：链表的头节点或第一个节点（在本例中为 4）

4 -> 6 -> 7 -> 1 -> 5 - > 8 -> 3 -> 2 -> NULL

返回

2 -> 3 -> 8 -> 5 -> 1 -> 7 -> 6 -> 4 -> NULL

给定

3 -> NULL

返回

3 -> NULL

给定

NULL

返回

NULL

有两种方法可以解决这个问题。这两种方法是：

1. 迭代方法
2. 递归方法

让我们先讨论迭代方法。

使用迭代方法反转链表

迭代方法涉及以下步骤。

步骤 1：定义三个指针（previous、current 和 next），并将它们初始化如下。

previous = NULL, current = head, next = NULL。

步骤 2：使用循环遍历链表，并执行以下操作。

实施

以下代码显示了使用上述步骤实现链表反转的方法。

文件名：LinkedListIterative.java

输出

The Linked list before reversal is: 
4 6 7 1 5 8 3 2 

After reversal, the linked list is: 
2 3 8 5 1 7 6 4

时间与空间复杂度：上述程序的 time complexity 为 O(n)，而 space complexity 为 O(1)，其中 n 代表列表中节点的总数。

使用递归方法反转链表

递归方法涉及以下步骤。

步骤 1：将给定的列表分成两部分——第一个节点和链表的其余部分。

步骤 2：为链表的其余部分调用 reverseList() 方法。

步骤 3：将其余部分连接到第一个节点。

步骤 4：固定头指针。

实施

以下代码显示了使用上述步骤实现链表反转的方法。

文件名：LinkedListRecursive.java

输出

The Linked list before reversal is: 
4 6 7 1 5 8 3 2 
 
After reversal, the linked list is: 
2 3 8 5 1 7 6 4

时间与空间复杂度：上述程序的 time complexity 为 O(n)，而 space complexity 为 O(1)，其中 n 代表列表中节点的总数。请注意，上述程序使用内置堆栈，因为它是递归的。为简单起见，我们忽略了内置堆栈占用的空间。

使用堆栈反转链表

当使用堆栈反转链表时，会用到以下步骤。

步骤 1：将节点的值存储在堆栈中，直到所有节点的值都已录入。

步骤 2：使用列表中最后一个节点的值更新头指针。

步骤 3：不断从堆栈中移除节点值，并将它们附加到头节点，直到堆栈为空。

步骤 4：确保在附加工作完成后，列表的最后一个节点指向 NULL。

实施

以下代码显示了使用上述步骤实现链表反转的方法。

文件名：LinkedListStack.java

输出

The Linked list before reversal is: 
4 6 7 1 5 8 3 2 
 
After reversal, the linked list is: 
2 3 8 5 1 7 6 4

时间与空间复杂度：上述程序的 time complexity 为 O(n)，而 space complexity 也为 O(n)，其中 n 代表列表中节点的总数。

使用数组反转链表

当使用数组反转链表时，会用到以下步骤。

步骤 1：计算给定列表中节点的数量。

步骤 2：创建一个整数数组，其大小等于列表的大小。

步骤 3：遍历列表，并使用从左到右的节点值填充数组。

步骤 4：从数组的末尾逐个取数组元素，并从中创建一个列表，使得数组的最后一个元素构成列表的头节点。数组的倒数第二个元素构成列表的第二个节点，依此类推。

实施

以下代码显示了使用上述步骤实现链表反转的方法。

文件名：LinkedListArray.java

输出

The Linked list before reversal is: 
4 6 7 1 5 8 3 2 
 
After reversal, the linked list is: 
2 3 8 5 1 7 6 4

时间与空间复杂度：上述程序的 time complexity 为 O(n)，而 space complexity 也为 O(n)，其中 n 代表列表中节点的总数。