本文深入探讨了在java中实现单向链表反转时可能遇到的`outofmemoryerror`。该错误通常源于不正确的反转逻辑导致链表形成循环，进而使遍历方法（如`tostring()`）陷入无限循环，不断消耗堆内存。文章将详细分析错误原因，并提供一种高效且正确的迭代法链表反转算法及其java实现。
理解OutOfMemoryError的根源
在Java中，当程序尝试分配超出Java虚拟机(JVM)堆内存限制的对象时，就会抛出java.lang.OutOfMemoryError: Java heap space。对于链表操作而言，这种错误通常不是因为链表本身节点过多，而是因为某种操作导致了无限循环，在循环内部持续创建对象或拼接字符串，最终耗尽堆内存。
在本例中，OutOfMemoryError的堆栈跟踪清晰地指向了StringBuilder.append()方法，该方法在MyCodeLink.toString()中被调用。这意味着，当调用toString()方法尝试打印链表内容时，它进入了一个无限循环，不断向StringBuilder追加字符，直到耗尽所有可用堆空间。
那么，为什么toString()会进入无限循环呢？原因在于reversal()方法的错误实现导致了链表中出现了循环引用。
问题代码分析
原始reversal()方法存在逻辑缺陷，其核心代码段如下：
立即学习“Java免费学习笔记（深入）”；
public void reversal(){
Node p1 = this.head;
Node p2 = p1.next;
while (p2 != null){
Node temp = p2.next;
p2.next = p1; // 关键问题所在：p2的next指向p1
p1 = p2;
p2 = temp;
}
this.head = p1;
}假设链表初始状态为 A -> B -> C -> D -> null。 当 p1 为 A，p2 为 B 时：
- temp = p2.next (即 C)
- p2.next = p1 (即 B.next 指向 A)。此时，链表局部变为 A B。
- p1 = p2 (即 p1 变为 B)
- p2 = temp (即 p2 变为 C)
现在，p1 是 B，p2 是 C。在下一次循环中，C.next 会指向 B。 问题在于，当 p1 和 p2 分别指向原始链表的第一个和第二个节点时，p2.next = p1 这一行使得第二个节点指向了第一个节点。然而，原始的第一个节点（即this.head）的next指针仍然指向第二个节点。这就形成了一个 head -> head.next -> head 的循环（例如 A -> B -> A）。
一旦链表中存在循环，任何尝试遍历整个链表的算法（如toString()方法）都将无限次地访问这些循环节点，永远无法到达链表末尾的null，从而导致无限循环，最终耗尽内存。
正确的链表反转算法：迭代法
链表反转的经典方法是迭代法，它通过维护三个指针来实现：current（当前节点）、previous（前一个节点）和 next_temp（下一个节点）。其基本思想是在遍历链表的同时，将当前节点的next指针指向其previous节点。
以下是迭代法实现链表反转的步骤：
- 初始化 previous 指针为 null，它将作为反转后链表的尾部。
- 初始化 current 指针为 head，它将遍历原始链表。
- 循环直到 current 为 null：
- 保存 current.next 到 next_temp，以便在修改 current.next 后仍能继续遍历。
- 将 current.next 指向 previous，完成当前节点的反转。
- 更新 previous 为 current，为下一个节点的反转做准备。
- 更新 current 为 next_temp，移动到下一个节点。
- 循环结束后，previous 指针将指向反转后链表的新的头节点。将 this.head 更新为 previous。
示例代码：迭代法实现链表反转
根据上述算法，reversal()方法可以正确实现如下：
import java.util.ArrayList;
class Node {
public int val;
public Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
public Node(int val) {
this(val, null);
}
// setVal和setNext方法应为public或default，以便在MyCodeLink中访问
// 但在链表反转的常见实现中，直接访问字段更常见
// 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();
}
public void reversal() {
Node previous = null;
Node current = this.head;
while (current != null) {
Node nextTemp = current.next; // 暂存下一个节点
current.next = previous; // 反转当前节点的next指针
previous = current; // previous向前移动到当前节点
current = nextTemp; // current向前移动到下一个节点
}
this.head = previous; // 更新头节点为原链表的尾节点（反转后的头节点）
}
public static void main(String[] args) {
MyCodeLink myCodeLink = new MyCodeLink(8);
System.out.println("初始链表 size: " + myCodeLink.getSize());
System.out.println("初始链表: " + myCodeLink); // 输出: 8
myCodeLink.insertToHead(6);
System.out.println("插入头部后 size: " + myCodeLink.getSize());
System.out.println("插入头部后: " + myCodeLink); // 输出: 6 8
myCodeLink.insert(1, 7);
System.out.println("插入中间后 size: " + myCodeLink.getSize());
System.out.println("插入中间后: " + myCodeLink); // 输出: 6 7 8
myCodeLink.insertToLast(9);
System.out.println("插入尾部后 size: " + myCodeLink.getSize());
System.out.println("插入尾部后: " + myCodeLink); // 输出: 6 7 8 9
System.out.println("\n执行反转操作...");
myCodeLink.reversal();
System.out.println("反转后链表 size: " + myCodeLink.getSize());
System.out.println("反转后链表: " + myCodeLink); // 输出: 9 8 7 6
}
}运行上述代码，将得到以下输出：
初始链表 size: 1 初始链表: 8 插入头部后 size: 2 插入头部后: 6 8 插入中间后 size: 3 插入中间后: 6 7 8 插入尾部后 size: 4 插入尾部后: 6 7 8 9 执行反转操作... 反转后链表 size: 4 反转后链表: 9 8 7 6
可以看到，链表已成功反转，且不再出现OutOfMemoryError。
注意事项与最佳实践
- 调试链表问题： 对于链表相关的复杂操作，强烈建议在纸上画出链表的每个节点及其指针的变化过程。这有助于直观地理解算法逻辑，并发现潜在的循环或断链问题。
- 边界条件： 在实现链表操作时，务必考虑各种边界条件，例如空链表、只有一个节点的链表、在头部或尾部插入/删除等。
- 引用管理： 链表操作本质上是对节点引用的管理。确保在修改next指针时，不会丢失对后续节点的引用，也不会创建循环引用。
- Java垃圾回收： 虽然Java有自动垃圾回收机制，但如果程序逻辑错误导致对象无法被回收（例如，链表循环导致所有节点都“可达”），仍然可能导致内存泄漏或OutOfMemoryError。
- 替代反转方法： 除了迭代法，链表反转还可以通过递归实现。然而，递归方法通常需要额外的栈空间，对于非常长的链表可能会导致StackOverflowError，因此迭代法在生产环境中更为常用。
通过理解OutOfMemoryError的根本原因并采用正确的迭代法反转算法，可以有效地避免此类问题，并编写出健壮的链表操作代码。
