在java中实现链表反转时，如果逻辑不当，可能导致创建循环链表，进而引发`outofmemoryerror`。本文将深入分析错误的链表反转实现如何造成内存溢出，并提供一种标准、高效的迭代法，通过巧妙的指针操作，实现链表的正确反转，同时避免不必要的内存消耗。
链表反转概述
链表反转是数据结构中一个常见的操作，其目标是将一个单向链表的节点顺序颠倒。例如，一个链表 A -> B -> C 经过反转后应变为 C -> B -> A。实现这一操作通常需要仔细管理节点之间的next指针。
OutOfMemoryError的根本原因分析
在提供的代码示例中，reversal() 方法的实现存在一个严重的逻辑错误，导致了java.lang.OutOfMemoryError: Java heap space。这个错误并非直接由reversal()方法本身消耗大量内存引起，而是其副作用——创建了一个循环链表，进而影响了其他操作，特别是toString()方法。
让我们分析原始的错误实现：
public void reversal(){
Node p1 = this.head;
Node p2 = p1.next;
while (p2 != null){
Node temp = p2.next;
p2.next = p1; // 错误发生点：p2指向p1
p1 = p2;
p2 = temp;
}
this.head = p1;
}假设链表初始状态为 A -> B -> C -> D：
立即学习“Java免费学习笔记（深入）”；
- 初始化： p1 指向 A，p2 指向 B。
-
第一次循环：
- temp 指向 C。
- p2.next = p1; 这行代码将 B 的 next 指针指向 A。此时，链表结构局部变为 A -> B -> A。
- 关键问题： 此时，A 的 next 指针仍然指向 B。因此，实际上形成了一个循环：A B。
- p1 更新为 B。
- p2 更新为 C。
- 后续循环： 虽然 p1 和 p2 会继续向前移动，但 A B 这个循环已经形成并存在于链表的头部。
当链表反转完成后，如果调用 toString() 方法来打印链表：
@Override
public String toString(){
StringBuilder s = new StringBuilder();
Node cur = head;
while (cur != null){ // 这个循环将永远不会结束
s.append(cur.val).append("\t");
cur = cur.next;
}
return s.toString();
}由于链表头部的 A B 循环，toString() 方法中的 while (cur != null) 条件将永远为真。cur 会在 A 和 B 之间无限循环，导致 StringBuilder 不断地追加字符，最终耗尽Java堆空间，抛出 OutOfMemoryError。
关于注释掉的ArrayList实现： 原始代码中也包含了一个使用 ArrayList 存储节点的反转尝试。虽然这种方法不会导致循环，但它需要额外的 O(N) 空间来存储所有节点（其中 N 是链表的长度）。对于非常长的链表，这种方法同样可能导致 OutOfMemoryError，因为它会在堆上分配一个与链表长度成正比的 ArrayList。
正确的迭代法链表反转
解决上述问题的标准方法是使用迭代法，通过三个指针 (previous, current, nextTemp) 来实现链表的反转，其空间复杂度为 O(1)。
以下是正确的 reversal() 方法实现：
public void reversal(){
Node current = this.head; // 当前正在处理的节点
Node previous = null; // 前一个节点，反转后将成为当前节点的下一个节点
while (current != null){
Node nextTemp = current.next; // 临时保存当前节点的下一个节点，以便后续移动
current.next = previous; // 将当前节点的next指针指向前一个节点，完成反转
previous = current; // previous指针向前移动，指向当前节点
current = nextTemp; // current指针向前移动，指向下一个待处理节点
}
this.head = previous; // 循环结束后，previous将指向原链表的最后一个节点，即新链表的头节点
}工作原理详解：
-
初始化：
- current 指向链表的头节点 (A)。
- previous 初始化为 null，因为反转后原头节点将成为尾节点，其 next 指针应为 null。
-
循环过程：
- 保存下一个节点： nextTemp = current.next; 这一步至关重要，它在修改 current.next 之前，保存了原链表中 current 的下一个节点，确保我们不会丢失链表的后续部分。
- 反转指针： current.next = previous; 这是核心操作，将 current 节点的 next 指针从原来的指向“前方”改为指向“后方”（即 previous 节点）。
- 移动 previous： previous = current; 将 previous 指针更新为当前已经反转的节点，为下一次循环做准备。
- 移动 current： current = nextTemp; 将 current 指针更新为下一个待处理的节点。
- 循环终止： 当 current 变为 null 时，表示所有节点都已处理完毕。此时，previous 指针将指向原链表的最后一个节点，它现在是新链表的头节点。
- 更新头节点： this.head = previous; 将链表的头节点更新为 previous，完成反转。
完整示例代码
下面是包含正确 reversal() 方法的 MyCodeLink 类完整代码：
package com.company;
import java.util.ArrayList;
class Node {
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
public Node(int val) {
this(val, null);
}
int val;
Node next;
// private setters are generally not recommended for public facing Node class
// but keeping for consistency with original code structure.
private void setVal(int newVal) {
this.val = newVal;
}
private void setNext(Node newNextNode) {
this.next = newNextNode;
}
}
public class MyCodeLink {
private Node head;
private int size;
public MyCodeLink(int val) {
this.head = new Node(val, null);
this.size = 1;
}
public void insert(int index, int val) {
if (index < 0 || index > this.getSize()) {
throw new IndexOutOfBoundsException("index must >= 0 and <= size");
}
if (index == 0) {
this.head = new Node(val, head);
this.size++;
return;
}
Node cur = head;
for (int i = 0; i < index - 1; i++) {
cur = cur.next;
}
Node node = new Node(val, cur.next);
cur.next = node;
this.size++;
}
public void insertToHead(int val) {
insert(0, val);
}
public void insertToLast(int val) {
insert(this.getSize(), val);
}
public int getSize() {
return this.size;
}
public Node getHead() {
return head;
}
@Override
public String toString() {
StringBuilder s = new StringBuilder();
Node cur = head;
while (cur != null) {
s.append(cur.val).append("\t");
cur = cur.next;
}
return s.toString();
}
/**
* Correctly reverses the linked list using an iterative approach.
* Time Complexity: O(N)
* Space Complexity: O(1)
*/
public void reversal() {
Node current = this.head;
Node previous = null;
while (current != null) {
Node nextTemp = current.next; // Save the next node
current.next = previous; // Reverse the current node's pointer
previous = current; // Move previous one step forward
current = nextTemp; // Move current one step forward
}
this.head = previous; // Update the head of the list
}
public static void main(String[] args) {
MyCodeLink myCodeLink = new MyCodeLink(8);
System.out.println("Initial list:");
System.out.println("size: " + myCodeLink.getSize());
System.out.println(myCodeLink); // Output: 8
myCodeLink.insertToHead(6);
System.out.println("\nAfter insertToHead(6):");
System.out.println("size: " + myCodeLink.getSize());
System.out.println(myCodeLink); // Output: 6 8
myCodeLink.insert(1, 7);
System.out.println("\nAfter insert(1, 7):");
System.out.println("size: " + myCodeLink.getSize());
System.out.println(myCodeLink); // Output: 6 7 8
myCodeLink.insertToLast(9);
System.out.println("\nAfter insertToLast(9):");
System.out.println("size: " + myCodeLink.getSize());
System.out.println(myCodeLink); // Output: 6 7 8 9
System.out.println("\nReversing the list...");
myCodeLink.reversal();
System.out.println("List after reversal:");
System.out.println("size: " + myCodeLink.getSize());
System.out.println(myCodeLink); // Output: 9 8 7 6
}
}注意事项与总结
- 指针操作的精确性： 链表操作的核心在于对 next 指针的精确控制。任何微小的错误都可能导致链表断裂、循环或数据丢失。在实现链表操作时，建议画图辅助理解指针的移动。
-
边界条件： 考虑空链表、单节点链表等边界情况。上述迭代反转算法能够正确处理这些情况：
- 如果 head 为 null，current 初始即为 null，循环不执行，this.head 仍为 null，正确。
- 如果链表只有一个节点，current 指向该节点，previous 为 null。第一次循环后，该节点 next 指向 null，previous 指向该节点，current 为 null。最终 this.head 指向该节点，正确。
- 空间复杂度： 正确的迭代反转方法仅使用了几个额外的指针变量，因此其空间复杂度为 O(1)，非常高效。相比之下，使用 ArrayList 存储所有节点的方法空间复杂度为 O(N)，对于大规模链表可能导致内存问题。
- 错误排查： 当遇到 OutOfMemoryError 时，除了检查直接内存分配外，还应考虑是否存在无限循环或过度递归，这些情况会导致内存或栈空间被耗尽。
通过理解和应用正确的迭代法链表反转算法，可以有效避免因逻辑错误导致的OutOfMemoryError，并确保链表操作的健壮性和效率。
