Java链表反转内存溢出解决方法

本篇文章向大家介绍《Java链表反转内存溢出问题解析》，主要包括，具有一定的参考价值，需要的朋友可以参考一下。

在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：

1. 初始化： p1 指向 A，p2 指向 B。
2. 第一次循环：
   • temp 指向 C。
   • p2.next = p1; 这行代码将 B 的 next 指针指向 A。此时，链表结构局部变为 A -> B -> A。
   • 关键问题： 此时，A 的 next 指针仍然指向 B。因此，实际上形成了一个循环：A <-> B。
   • p1 更新为 B。
   • p2 更新为 C。
3. 后续循环： 虽然 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将指向原链表的最后一个节点，即新链表的头节点
}

工作原理详解：

1. 初始化：
   • current 指向链表的头节点 (A)。
   • previous 初始化为 null，因为反转后原头节点将成为尾节点，其 next 指针应为 null。
2. 循环过程：
   • 保存下一个节点： nextTemp = current.next; 这一步至关重要，它在修改 current.next 之前，保存了原链表中 current 的下一个节点，确保我们不会丢失链表的后续部分。
   • 反转指针： current.next = previous; 这是核心操作，将 current 节点的 next 指针从原来的指向“前方”改为指向“后方”（即 previous 节点）。
   • 移动 previous： previous = current; 将 previous 指针更新为当前已经反转的节点，为下一次循环做准备。
   • 移动 current： current = nextTemp; 将 current 指针更新为下一个待处理的节点。
3. 循环终止： 当 current 变为 null 时，表示所有节点都已处理完毕。此时，previous 指针将指向原链表的最后一个节点，它现在是新链表的头节点。
4. 更新头节点： 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
    }
}

注意事项与总结

1. 指针操作的精确性： 链表操作的核心在于对 next 指针的精确控制。任何微小的错误都可能导致链表断裂、循环或数据丢失。在实现链表操作时，建议画图辅助理解指针的移动。
2. 边界条件： 考虑空链表、单节点链表等边界情况。上述迭代反转算法能够正确处理这些情况：
   • 如果 head 为 null，current 初始即为 null，循环不执行，this.head 仍为 null，正确。
   • 如果链表只有一个节点，current 指向该节点，previous 为 null。第一次循环后，该节点 next 指向 null，previous 指向该节点，current 为 null。最终 this.head 指向该节点，正确。
3. 空间复杂度： 正确的迭代反转方法仅使用了几个额外的指针变量，因此其空间复杂度为 O(1)，非常高效。相比之下，使用 ArrayList 存储所有节点的方法空间复杂度为 O(N)，对于大规模链表可能导致内存问题。
4. 错误排查： 当遇到 OutOfMemoryError 时，除了检查直接内存分配外，还应考虑是否存在无限循环或过度递归，这些情况会导致内存或栈空间被耗尽。

通过理解和应用正确的迭代法链表反转算法，可以有效避免因逻辑错误导致的OutOfMemoryError，并确保链表操作的健壮性和效率。

理论要掌握，实操不能落！以上关于《Java链表反转内存溢出解决方法》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！