链表反转的核心是调整每个节点的next指针方向，1. 迭代法使用三个指针prev、curr和nexttemp，通过循环将每个节点的next指向前一个节点，最终prev指向新头节点，时间复杂度o(n)，空间复杂度o(1)；2. 递归法基于“先反转后续链表再调整当前节点”的思想，基本情况是空节点或单节点，递归反转head.next后，将head.next.next指向head并置head.next为null，返回原链表尾节点作为新头，时间复杂度o(n)，空间复杂度o(n)；实际开发中需注意空链表和单节点的边界处理、指针顺序维护以防链表断裂，首选迭代法以避免递归导致的栈溢出风险，两种方法均需确保正确引用节点以利于gc回收，此操作完整实现了链表基础定义与核心操作的综合应用。
链表反转，在Java代码里实现，核心其实就是调整每个节点的
next
指针方向。这不像数组反转那么直接，你不能简单地交换元素位置，因为链表是靠指针串联起来的。所以，我们得小心翼翼地把每个节点指向它原本的前一个节点，而不是后一个。至于链表的基础操作，无非就是节点的定义、插入、删除和遍历，这些都是为了能玩转链表而必须掌握的。
解决方案
要实现链表的反转，最常用也最稳妥的方法就是迭代法。这个方法不需要额外的存储空间（除了几个指针变量），而且效率很高。
想象一下，你有一串珠子，它们被一根线串起来。现在你想让这串珠子反过来，你就得把线从每个珠子后面抽出来，再从前面穿进去。在代码里，这根“线”就是
next
指针。
立即学习“Java免费学习笔记（深入）”；
我们需要三个指针来完成这个“穿线”的过程：
-
prev
(previous): 指向当前节点的前一个节点。一开始，它什么都没有，所以是
null
。
-
curr
(current): 指向我们正在处理的当前节点。一开始，它就是链表的头节点。
-
nextTemp
(next temporary): 这是一个临时指针，用来保存
curr
节点的下一个节点。为什么需要它？因为我们马上就要改变
curr.next
的指向了，如果不提前存起来，我们就找不到下一个要处理的节点了。
循环会一直进行，直到
curr
变成
null
，这意味着我们已经遍历了整个链表。在每一次循环中：
- 我们先用
nextTemp
把
curr
的下一个节点“记住”。
- 然后，把
curr
的
next
指针指向
prev
。这是反转的核心一步。
- 接着，
prev
向前移动，变成当前的
curr
。
- 最后，
curr
也向前移动，变成之前用
nextTemp
记住的那个节点。
这样一步步走下来，当循环结束时，
prev
指针就会指向原链表的最后一个节点，也就是反转后链表的头节点。
class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class LinkedListReversal { /** * 迭代法反转链表 * * @param head 链表的头节点 * @return 反转后链表的头节点 */ public ListNode reverseListIterative(ListNode head) { ListNode prev = null; // 指向前一个节点，初始为null ListNode curr = head; // 指向当前节点，初始为链表头 while (curr != null) { ListNode nextTemp = curr.next; // 临时保存当前节点的下一个节点 curr.next = prev; // 将当前节点的next指针指向前一个节点，实现反转 prev = curr; // prev指针向前移动，指向当前节点 curr = nextTemp; // curr指针向前移动，指向下一个待处理的节点 } return prev; // 循环结束后，prev就是新链表的头节点 } // 辅助方法：打印链表 public void printList(ListNode head) { ListNode current = head; while (current != null) { System.out.print(current.val + " -> "); current = current.next; } System.out.println("null"); } public static void main(String[] args) { LinkedListReversal reverser = new LinkedListReversal(); // 构建一个链表: 1 -> 2 -> 3 -> 4 -> 5 ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); head.next.next.next = new ListNode(4); head.next.next.next.next = new ListNode(5); System.out.print("原始链表: "); reverser.printList(head); // 反转链表 ListNode reversedHead = reverser.reverseListIterative(head); System.out.print("反转后链表: "); reverser.printList(reversedHead); // 测试空链表和单节点链表 System.out.println("n--- 测试特殊情况 ---"); System.out.print("空链表反转: "); reverser.printList(reverser.reverseListIterative(null)); System.out.print("单节点链表反转: "); reverser.printList(reverser.reverseListIterative(new ListNode(100))); } }
链表在Java中如何定义和实现基础操作？
在Java里，链表本身并不是一个内置的数据结构，我们通常是通过自定义的
Node
（或
ListNode
）类来构建它。一个最简单的链表节点，至少需要两个东西：一个用来存数据的值（比如
int val
），另一个就是指向下一个节点的引用（
ListNode next
）。
// 这是最基本的节点定义，上面已经有了，这里再强调一下 class ListNode { int val; // 节点存储的数据 ListNode next; // 指向下一个节点的引用 ListNode(int x) { val = x; next = null; // 构造新节点时，默认下一个是空的 } }
有了节点，我们就可以实现一些基础操作了。这些操作是理解和操作链表的基础，说实话，很多时候链表的题目就是围绕这些基本操作的变种。
-
插入节点 (在尾部)： 如果你想在链表末尾加一个新节点，你需要从头开始遍历，直到找到最后一个节点（就是
next
为
null
的那个），然后把新节点挂在它后面。
public void addNodeAtEnd(ListNode head, int val) { ListNode newNode = new ListNode(val); if (head == null) { // 如果链表是空的，新节点就是头 // 实际上，这里需要一个外部变量来更新head， // 否则在方法内部更新head不会影响外部引用 // 通常我们会有一个LinkedList类来管理head // 简单起见，这里假设head是传入的第一个节点 return; // 实际应用中，会返回newNode作为新的head } ListNode current = head; while (current.next != null) { current = current.next; } current.next = newNode; } -
插入节点 (在头部)： 这个就简单多了。创建一个新节点，让它的
next
指向当前的头节点，然后把这个新节点设为新的头节点。
public ListNode addNodeAtBeginning(ListNode head, int val) { ListNode newNode = new ListNode(val); newNode.next = head; return newNode; // 新的头节点 } -
删除节点 (按值)： 要删除一个特定值的节点，你得遍历链表。如果找到匹配的节点，你需要把它的前一个节点的
next
指针直接指向被删除节点的下一个节点，这样就“跳过”了那个要删除的节点。如果删除的是头节点，那就直接把头节点指向它的下一个。
public ListNode deleteNodeByValue(ListNode head, int val) { if (head == null) { return null; } if (head.val == val) { // 如果头节点就是要删除的 return head.next; } ListNode current = head; while (current.next != null && current.next.val != val) { current = current.next; } if (current.next != null) { // 找到了要删除的节点 current.next = current.next.next; } return head; } -
遍历链表 (打印)： 这个是最基础的，从头节点开始，沿着
next
指针一个接一个地访问，直到遇到
null
。
// 已经包含在上面的示例代码中 public void printList(ListNode head) { ListNode current = head; while (current != null) { System.out.print(current.val + " -> "); current = current.next; } System.out.println("null"); }这些操作，说白了，就是围绕着
head
和各个节点的
next
指针做文章。理解了这些，链表的问题就没那么神秘了。
链表反转操作的两种常见实现思路是什么？
除了上面详细讲的迭代法，链表反转还有另一种非常经典的实现思路——递归法。这两种方法各有特点，理解它们能让你对链表操作的理解更上一层楼。
1. 迭代法 (Iterative Approach)
这个我们上面已经详细讲过了，它的核心思想就是“三指针”大法：
prev
、
curr
、
nextTemp
。一步步地改变当前节点的
next
指向，同时移动这三个指针，直到遍历完整个链表。
- 优点：
- 空间复杂度是O(1)，因为它只用了常数个额外的指针变量。对于很长的链表，这非常重要，不会有栈溢出的风险。
- 性能稳定，没有递归调用栈的开销。
- 缺点：
- 逻辑上可能比递归稍微难理解一点点，需要脑子里清晰地模拟指针的移动过程。
2. 递归法 (Recursive Approach)
递归法反转链表，初看起来可能有点绕，但一旦理解了它的精髓，你会觉得它非常巧妙。它的基本思想是：
- 基本情况 (Base Case)：如果链表是空的（
head == null
）或者只有一个节点（
head.next == null
），那它本身就是反转的，直接返回
head
。这是递归的终止条件。
- 递归步骤 (Recursive Step)：对于一个非空且不止一个节点的链表，我们假设除了头节点之外的“剩余部分”（
head.next
）已经通过递归调用被反转了。那么，现在我们只需要把当前头节点
head
接到反转后的“剩余部分”的尾巴上。
具体来说：
-
newHead = reverseListRecursive(head.next);
这行代码会一直递归下去，直到链表的最后一个节点，并把这个最后一个节点作为
newHead
返回。
- 当递归开始向上返回时，比如当前处理的是节点A，它的下一个是节点B。递归调用已经把B以及B后面的所有节点都反转了。现在
head
是A，
head.next
是B。反转后的B及其后面的链表，其头部是原来的尾部。
- 我们要做的是让B的
next
指向A，即
head.next.next = head;
。
- 然后，A的
next
应该指向
null
，因为A现在是它所在局部反转链表的尾部，即
head.next = null;
。
- 最后，返回最开始递归调用时得到的那个
newHead
，它就是整个链表反转后的新头。
public ListNode reverseListRecursive(ListNode head) { // 基本情况：链表为空或只有一个节点，直接返回 if (head == null || head.next == null) { return head; } // 递归反转head.next开始的子链表 // newHead会是原链表的最后一个节点，也是反转后链表的头节点 ListNode newHead = reverseListRecursive(head.next); // 完成当前节点的反转： // head.next (即原链表的下一个节点) 的 next 指向 head // 比如 1 -> 2 -> 3，当处理到1时，newHead是3。 // 此时 head=1, head.next=2。 // 递归返回时，2 -> 3 已经反转成 3 -> 2。 // 现在 2 的 next 指向 1 (head.next.next = head;) // 1 的 next 指向 null (head.next = null;) head.next.next = head; head.next = null; return newHead; // 每次都返回最开始的那个新头节点 }
- 优点：
- 代码看起来更简洁、优雅，符合函数式编程的思维。
- 缺点：
- 空间复杂度是O(N)，因为每次递归调用都会占用栈空间，链表越长，栈深度越大。对于非常长的链表，可能会导致栈溢出（StackOverflowError）。
- 性能上通常不如迭代法，有额外的函数调用开销。
在实际开发中，如果对链表长度没有严格限制，或者担心栈溢出，迭代法通常是更稳妥的选择。但如果你觉得递归的逻辑更清晰，且链表长度可控，递归法也未尝不可。
在实际开发中，链表反转的常见陷阱和性能考量有哪些？
在实际操作链表反转时，有一些细节和潜在问题是需要注意的，特别是对于那些初学者来说，一不小心就可能掉进坑里。
1. 空链表和单节点链表 这是最常见的边缘情况。如果传入的
head
是
null
（空链表），或者
head.next
也是
null
（单节点链表），你的反转逻辑必须能够正确处理。
- 陷阱：很多新手在写循环或递归时，没有考虑
head == null
或
head.next == null
的情况，导致空指针异常。
- 处理：迭代法中，
while (curr != null)
自然会处理空链表，因为
curr
一开始就是
null
，循环不执行，直接返回
prev
（也就是
null
）。单节点链表也是一样，循环一次就结束，
prev
会是那个唯一的节点。递归法中，
if (head == null || head.next == null)
就是专门处理这些基本情况的。
2. 指针的正确维护 这是链表操作的核心，也是最容易出错的地方。
- 陷阱：在迭代法中，如果你没有先用
nextTemp
保存
curr.next
，然后直接修改了
curr.next
的指向，那么你就失去了对链表后续部分的引用，链表就“断”了。
- 处理：务必牢记“三指针”的顺序和作用：先保存下一个，再反转当前，最后移动指针。
3. 内存管理 (Java中的GC) 虽然Java有垃圾回收机制（GC），不像C/C++那样需要手动
free
内存，但理解其原理有助于避免潜在的内存泄漏（虽然在链表反转中不常见）。
- 陷阱：如果你在反转过程中不小心丢失了对某些节点的引用，它们就可能变成“孤儿”节点，虽然会被GC回收，但如果逻辑错误导致大量节点无法被正确引用，可能会造成短暂的内存压力。
- 处理：确保所有节点在反转前后都能被正确引用，或者被GC识别为可回收。在链表反转中，只要你正确地调整了
next
指针，所有节点最终都会被新链表引用，或者被GC回收。
4. 性能考量
- 时间复杂度：无论是迭代法还是递归法，它们都需要遍历链表中的每一个节点一次。所以，它们的时间复杂度都是O(N)，其中N是链表的长度。这是最优的，因为你至少要访问每个节点一次才能完成反转。
- 空间复杂度：
- 迭代法：O(1)。它只需要常数个额外的指针变量来完成操作，不依赖于链表长度。这是它最大的优势。
- 递归法：O(N)。每次递归调用都会在函数调用栈中创建一个新的栈帧，链表有多长，递归深度就有多深。对于非常长的链表（比如几十万个节点），这可能导致栈溢出错误（StackOverflowError）。
- 选择依据：
- 首选迭代法：在绝大多数实际开发场景中，迭代法是更推荐的选择，因为它没有栈溢出的风险，且空间效率更高。
- 递归法的适用场景：如果你确信链表长度不会太长（比如几千个节点以内），或者你更看重代码的简洁性和递归思维的训练，那么递归法也是可以接受的。但在面试或生产环境中，通常会倾向于迭代法。
总之，链表反转看似简单，但它涵盖了链表操作的精髓和一些常见的编程陷阱。理解并能熟练运用迭代法，同时了解递归法的原理和局限性，对你的数据结构和算法功底会有很大的提升。
评论（已关闭）
评论已关闭