Java链表反转深度解析：迭代与递归方法详解及实践15

作为一名专业的程序员，在日常开发和面试中，链表（Linked List）无疑是最常见且重要的基础数据结构之一。而“链表反转”则是一个经典的算法问题，它不仅能考察你对链表基本操作的掌握，还能体现你对迭代与递归思想的理解和运用能力。本文将深入探讨Java中实现单向链表反转的两种核心方法：迭代法和递归法，并通过详细的代码示例、图解分析以及复杂度讨论，帮助你彻底理解并掌握这一核心技能。

一、链表基础：Java中的表示

在深入反转方法之前，我们首先需要明确链表的结构。单向链表由一系列节点组成，每个节点包含两部分：数据域（存储值）和指针域（指向下一个节点的引用）。链表的最后一个节点指向`null`。

在Java中，我们通常用一个内部类或单独的类来表示链表节点（ListNode）：
class ListNode {
int val; // 节点存储的值
ListNode next; // 指向下一个节点的引用
// 构造函数
ListNode() {}
ListNode(int val) { = val; }
ListNode(int val, ListNode next) { = val; = next; }
}

为了方便后续的测试和演示，我们也可以添加一个简单的链表构建和打印方法：
// 辅助方法：构建链表
public static ListNode createLinkedList(int[] arr) {
if (arr == null || == 0) {
return null;
}
ListNode head = new ListNode(arr[0]);
ListNode current = head;
for (int i = 1; i < ; i++) {
= new ListNode(arr[i]);
current = ;
}
return head;
}
// 辅助方法：打印链表
public static void printLinkedList(ListNode head) {
ListNode current = head;
while (current != null) {
( + " -> ");
current = ;
}
("null");
}

二、链表反转方法一：迭代法（Iterative Method）

迭代法是实现链表反转最常用且效率较高的方法。其核心思想是，在遍历链表的同时，逐个改变每个节点的`next`指针，使其指向前一个节点，而不是后一个节点。为了实现这一目标，我们需要维护几个关键的指针。

1. 思路与步骤

我们需要三个指针来完成迭代反转：
`prev` (previous)：指向当前节点的前一个节点。初始时为`null`，因为新链表的头节点（原链表的尾节点）后面是`null`。
`curr` (current)：指向当前正在处理的节点。初始时为链表的头节点`head`。
`nextTemp` (next temporary)：在修改``之前，用来临时保存`curr`的下一个节点，以防止链表断裂。

算法步骤如下：
初始化 `prev = null`， `curr = head`。
进入循环，条件是 `curr != null`：

a. 保存 `curr` 的下一个节点：`nextTemp = `。
b. 反转 `curr` 的 `next` 指针，使其指向 `prev`：` = prev`。
c. 移动 `prev` 指针：`prev = curr`。
d. 移动 `curr` 指针：`curr = nextTemp`。

循环结束后，`prev` 将指向原链表的最后一个节点，也就是新链表的头节点。返回 `prev`。

2. 图解过程

假设我们有一个链表：1 -> 2 -> 3 -> 4 -> null

初始状态：

prev = null

curr = 1

nextTemp = ?

第一步 (curr = 1):

nextTemp = 2

= null (反转)

prev = 1

curr = 2

链表状态：null 3 -> 4 -> null

第二步 (curr = 2):

nextTemp = 3

= 1 (反转)

prev = 2

curr = 3

链表状态：null null

第三步 (curr = 3):

nextTemp = 4

= 2 (反转)

prev = 3

curr = 4

链表状态：null node3 -> ... -> noden`。
基线条件 (Base Case)：

如果链表为空 (`head == null`)，或者链表只有一个节点 (` == null`)，那么它本身就是反转后的链表，直接返回 `head`。这是递归的终止条件。

递归关系 (Recursive Step)：

假设我们已经能够正确反转从 `` 开始的子链表，并得到了新的头节点 `newHead`。
那么，原链表的 `` (也就是 `node2`) 在反转后，会变成 `node2 -> head`。
因此，我们只需要将 `` 指向 `head`，就完成了 `node2` 和 `head` 之间的反转。
同时，为了避免循环引用（例如 `head -> node2` 变成 `head node2`），需要将 `` 设置为 `null`。
最后，返回 `newHead`，它是整个反转后链表的头节点。