本文深入探讨了在Java中实现单链表反转时可能遇到的`OutOfMemoryError`，该错误通常源于不正确的反转逻辑导致链表形成循环。我们将分析错误产生的原因，揭示原代码中循环引用的陷阱，并提供一种标准、高效且健壮的迭代方法来正确反转链表，确保其结构完整性。
链表反转中的OutOfMemoryError分析
在Java中实现链表反转时，如果遇到java.lang.OutOfMemoryError: Java heap space异常，并且堆栈跟踪指向StringBuilder.append()方法，这通常意味着链表结构中存在一个无限循环。当尝试通过toString()方法遍历并打印链表时，由于循环的存在，遍历操作无法终止，导致StringBuilder持续尝试追加元素，最终耗尽堆内存。
错误现象与堆栈跟踪
以下是一个典型的OutOfMemoryError堆栈跟踪，它表明问题发生在toString()方法中，而根本原因可能在于链表的结构被破坏：
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.base/java.util.Arrays.copyOf(Arrays.java:3537)
at java.base/java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:228)
at java.base/java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:829)
at java.base/java.lang.StringBuilder.append(StringBuilder.java:253)
at com.company.MyCodeLink.toString(MyCodeLink.java:74) // 指向toString方法
at java.base/java.lang.String.valueOf(String.java:4218)
at java.base/java.io.PrintStream.println(PrintStream.java:1047)
at com.company.MyCodeLink.main(MyCodeLink.java:132)这个错误提示清晰地表明StringBuilder在MyCodeLink.toString()方法中无限增长。在链表上下文中，这意味着toString()方法中的while (cur != null)循环未能正常退出，因为cur指针永远无法达到null，它在链表的一个循环中反复移动。
立即学习“Java免费学习笔记（深入）”；
原有反转方法的问题
分析原始的reversal()方法实现：
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 -> null：
- 初始化： head指向A，p1指向A，p2指向B。
-
第一次循环：
- p2 != null (B != null) 为真。
- temp指向C。
- p2.next = p1;：B的next指针现在指向A。此时，链表结构局部变为 A -> B 且 B -> A。注意：A的next指针仍然指向B，这形成了 A B 的循环。
- p1 = p2;：p1现在指向B。
- p2 = temp;：p2现在指向C。
- 后续循环： 如果第一次循环后A的next指针没有被正确处理，那么A和B之间会形成一个循环。当toString()方法从head（现在是B）开始遍历时，它会从B走到A，再从A走到B，无限循环下去。
问题在于，当p2.next = p1;执行时，我们只更新了p2的next指针，使其指向p1。但p1的next指针（即原始链表中的head.next）仍然指向p2（或原始链表的第二个节点）。这导致了第一个节点和第二个节点之间的双向引用，形成了一个循环。
正确的链表反转算法（迭代法）
为了正确地反转链表并避免循环引用，我们需要使用三个指针来跟踪当前节点、前一个节点和下一个节点。
算法思路
- current (当前节点): 初始化为链表的头节点。
- previous (前一个节点): 初始化为null，因为反转后，原头节点的next将指向null。
- temp (临时节点): 用于在修改current.next之前保存current的下一个节点，防止链表断裂。
在每次迭代中：
- 保存current的下一个节点到temp。
- 将current的next指针指向previous。
- 将previous更新为current（即，current成为下一个迭代的previous）。
- 将current更新为temp（即，移动到下一个节点）。
循环直到current变为null，此时previous将指向新的头节点。
示例代码
以下是采用标准迭代法实现的链表反转方法：
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);
}
}
public class MyCodeLink {
private Node head;
private int size;
public MyCodeLink(int val) {
this.head = new Node(val);
this.size = 1;
}
// ... (其他方法如insert, getSize, 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();
}
public void reversal() {
Node current = this.head; // 当前正在处理的节点
Node previous = null; // 反转后，当前节点的前一个节点
while (current != null) {
Node temp = current.next; // 1. 保存下一个节点，防止链表断裂
current.next = previous; // 2. 将当前节点的next指向前一个节点，完成反转
previous = current; // 3. 移动previous到当前节点
current = temp; // 4. 移动current到下一个节点
}
this.head = previous; // 循环结束后，previous就是新的头节点
}
public static void main(String[] args) {
MyCodeLink myCodeLink = new MyCodeLink(8);
myCodeLink.insertToHead(6); // 6 -> 8
myCodeLink.insert(1, 7); // 6 -> 7 -> 8
myCodeLink.insertToLast(9); // 6 -> 7 -> 8 -> 9
System.out.println("Original list: " + myCodeLink); // 6 7 8 9
myCodeLink.reversal();
System.out.println("Reversed list: " + myCodeLink); // 9 8 7 6
}
}关键点与注意事项
- 初始化previous为null： 这是至关重要的，因为反转后的新链表尾部（原链表头部）的next指针应该指向null。
- temp变量的作用： 在修改current.next之前，必须保存current.next的值。如果没有temp变量，一旦current.next被指向previous，我们就失去了对链表其余部分的引用。
- 指针移动顺序： current.next = previous; -> previous = current; -> current = temp; 这个顺序不能打乱，它确保了在每次迭代中，指针都能正确地更新，并且链表的连接关系得到正确修改。
- 更新head： 循环结束后，current会变成null，而previous会指向原链表的最后一个节点，也就是反转后的新头节点，因此需要将this.head更新为previous。
总结
OutOfMemoryError在链表操作中往往是结构性问题的信号，特别是循环引用的存在。通过理解链表反转的原理，并采用健壮的迭代方法（如上述三指针法），我们可以有效地避免此类错误，确保链表操作的正确性和程序的稳定性。在实现链表操作时，细致地管理节点间的next指针是避免逻辑错误的关键。
