Java链表反转实现：避免OutOfMemoryError与循环引用陷阱-java教程-PHP中文网

Java链表反转实现：避免OutOfMemoryError与循环引用陷阱

花韻仙語

发布： 2025-12-01 16:02:11

原创

393人浏览过

java链表反转实现：避免outofmemoryerror与循环引用陷阱

本文深入探讨了在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：

Fireflies.ai

自动化会议记录和笔记工具，可以帮助你的团队记录、转录、搜索和分析语音对话。

145

查看详情

初始化： 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。