Java链表反转错误引发内存溢出分析

本文深入探讨了Java单向链表反转操作中常见的`OutOfMemoryError`问题。通过分析一个错误的链表反转实现，揭示了因循环引用导致的无限遍历和内存耗尽的根本原因。文章提供了标准的三指针迭代法来正确反转链表，并详细解释了其工作原理，旨在帮助开发者避免此类错误，提升链表操作的健壮性。

1. 问题背景与现象分析

在实现单向链表反转功能时，开发者可能会遇到java.lang.OutOfMemoryError: Java heap space异常。这个异常通常不是直接发生在反转方法本身，而是发生在后续对链表进行遍历（例如通过toString()方法打印链表内容）时。这强烈暗示链表结构在反转后被破坏，形成了循环引用，导致遍历操作陷入无限循环，最终耗尽内存。

观察以下用户提供的代码片段，其中reversal()方法存在问题：

public void reversal(){
    Node p1 = this.head;
    Node p2 = p1.next;

    while (p2 != null){
        Node temp = p2.next;
        p2.next = p1; // 错误点：这里可能创建循环引用
        p1 = p2;
        p2 = temp;
    }

    this.head = p1;
}

以及在main方法中调用reversal()后，尝试打印链表时抛出的异常：

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) // 异常发生在这里
    // ... 其他堆栈信息

异常堆栈清晰地指向了MyCodeLink.toString()方法，表明在将链表内容追加到StringBuilder时发生了内存溢出。

2. 错误代码的详细分析

上述reversal()方法的错误在于对指针的更新逻辑。让我们以一个简单的链表 A -> B -> C -> null 为例进行分析：

1. 初始化:

   • head 指向 A
   • p1 指向 A
   • p2 指向 B

2. 第一次循环: (p2 即 B 不为 null)

   • temp 存储 p2.next (即 C)
   • p2.next = p1：此时 B.next 指向 A。注意：现在 A 和 B 互相指向，形成了 A <-> B 的循环。
   • p1 = p2：p1 指向 B
   • p2 = temp：p2 指向 C

3. 循环结束后的问题:

   • 在第一次循环结束后，链表变成了 A <-> B，而 C 仍然指向 null。
   • 原始的 head (即 A) 的 next 指针仍然指向 B。
   • this.head = p1 将 head 更新为 B。
   • 此时，链表实际上是 B -> A -> B -> A -> ...，并且 C 节点与链表脱离。
   • 当 toString() 方法从新的 head (即 B) 开始遍历时，它会先到 A，然后从 A 又回到 B，如此往复，形成一个无限循环。StringBuilder 不断追加字符，最终耗尽堆内存。

问题的核心在于 p2.next = p1; 这一步，它在没有完全断开原始链接的情况下，使得 p2 指向了 p1，从而在某些情况下（尤其是链表头部的两个节点）立即创建了循环引用。

3. 正确的单向链表反转实现

单向链表反转的经典方法是使用迭代法，通过维护三个指针（previous、current、next_temp）来逐步改变节点的next指针方向。

核心思想： 在遍历链表时，每次迭代都将当前节点的next指针指向其前一个节点。为了不丢失后续节点，我们需要在改变current.next之前，先保存current.next。

以下是正确的reversal()方法实现：

public void reversal(){
    Node current = this.head; // 当前正在处理的节点
    Node previous = null;    // 当前节点的前一个节点，初始为null

    while (current != null){
        Node nextTemp = current.next; // 1. 保存下一个节点，防止断链
        current.next = previous;      // 2. 将当前节点的next指针指向前一个节点，实现反转
        previous = current;           // 3. previous向前移动，成为下一个迭代的“前一个节点”
        current = nextTemp;           // 4. current向前移动，处理下一个节点
    }

    this.head = previous; // 循环结束后，previous指向原链表的最后一个节点，它现在是新链表的头
}

逐步解析： 我们继续以 A -> B -> C -> null 为例：

1. 初始化:

   • head 指向 A
   • current 指向 A
   • previous 指向 null

2. 第一次循环 (current = A):

   • nextTemp 存储 A.next (即 B)
   • A.next = previous (即 null)：现在 A 变成了新链表的尾部。
   • previous = current：previous 指向 A
   • current = nextTemp：current 指向 B
   • 链表状态：null <- A (B -> C -> null 仍然存在，但A已断开)

3. 第二次循环 (current = B):

   • nextTemp 存储 B.next (即 C)
   • B.next = previous (即 A)：现在 B 指向 A。
   • previous = current：previous 指向 B
   • current = nextTemp：current 指向 C
   • 链表状态：null <- A <- B (C -> null 仍然存在)

4. 第三次循环 (current = C):

   • nextTemp 存储 C.next (即 null)
   • C.next = previous (即 B)：现在 C 指向 B。
   • previous = current：previous 指向 C
   • current = nextTemp：current 指向 null
   • 链表状态：null <- A <- B <- C

5. 循环结束 (current = null):

   • while 条件 current != null 不满足，循环终止。
   • this.head = previous：将 head 更新为 previous，即 C。
   • 最终链表：C -> B -> A -> null，成功反转。

4. 完整的示例代码

以下是修正后的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;

    // 实际上，为了封装性，这些setter方法应在LinkedList类中操作，
    // 或者设计为package-private，但此处为简化示例保留。
    // 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();
    }

    /**
     * 正确的链表反转方法
     * 使用迭代法，通过三个指针 (previous, current, nextTemp) 完成反转
     */
    public void reversal() {
        Node current = this.head;
        Node previous = null;

        while (current != null) {
            Node nextTemp = current.next; // 1. 保存下一个节点
            current.next = previous;      // 2. 反转当前节点的next指针
            previous = current;           // 3. previous指针向前移动
            current = nextTemp;           // 4. current指针向前移动
        }

        this.head = previous; // 更新链表头为原链表的最后一个节点
    }

    public static void main(String[] args) {
        MyCodeLink myCodeLink = new MyCodeLink(8);

        System.out.println("Initial size: " + myCodeLink.getSize());
        System.out.println("Initial list: " + myCodeLink);

        myCodeLink.insertToHead(6);
        System.out.println("After insertToHead(6), size: " + myCodeLink.getSize());
        System.out.println("List: " + myCodeLink);

        myCodeLink.insert(1, 7);
        System.out.println("After insert(1, 7), size: " + myCodeLink.getSize());
        System.out.println("List: " + myCodeLink);

        myCodeLink.insertToLast(9);
        System.out.println("After insertToLast(9), size: " + myCodeLink.getSize());
        System.out.println("List: " + myCodeLink); // 此时链表应为 6 7 8 9

        System.out.println("\n--- Performing reversal ---");
        myCodeLink.reversal();
        System.out.println("After reversal, size: " + myCodeLink.getSize());
        System.out.println("Reversed list: " + myCodeLink); // 此时链表应为 9 8 7 6
    }
}

5. 注意事项与总结

1. 循环引用： 在链表操作中，尤其是涉及修改next指针时，务必警惕创建循环引用。一旦链表形成循环，遍历操作将陷入无限循环，最终可能导致OutOfMemoryError。
2. 指针顺序： 链表反转的关键在于正确地保存下一个节点、反转当前节点指针、并更新previous和current指针的顺序。任何顺序的错误都可能导致链表断裂或形成循环。
3. 边界条件： 考虑空链表 (head == null) 和只有一个节点的链表 (head.next == null) 的情况。上述迭代法能够正确处理这些边界情况，因为while (current != null)循环在这些情况下不会执行或只执行一次。
4. 空间复杂度： 迭代法反转链表的空间复杂度是O(1)，因为它只使用了常数个额外指针。如果使用栈（如问题代码中注释掉的ArrayList stack），则空间复杂度为O(N)，其中N是链表长度。在大多数情况下，迭代法是更优的选择。

通过本文的分析和正确实现，我们理解了单向链表反转中OutOfMemoryError的根本原因及其避免方法。掌握精确的指针操作是进行高效、健壮链表编程的关键。