递归实现链表连续重复元素删除时遇栈溢出问题求助

你的递归实现处理小规模链表能正常工作，但遇到大规模链表就触发栈溢出，核心原因是递归深度等于链表长度，当链表节点数量超过JVM调用栈的最大深度时，就会抛出StackOverflowError。

问题分析 #

当前递归逻辑是从链表头节点开始，每次递归调用处理head.next，链表有多少个节点就会产生多少层递归调用。每个递归调用都会在JVM的调用栈中创建一个方法栈帧，保存局部变量、返回地址等信息。而JVM的栈空间是有限的（默认通常在几百KB到几MB），当递归层数过多时，栈空间被耗尽，就会触发栈溢出。

解决方案：改用迭代实现 #

迭代方式不需要依赖调用栈，只使用常量级额外空间，能适配任意长度的链表，同时性能更优。修改后的代码如下：

/*
    Following is the Node class already written for the Linked List

    class Node<T> {
        T data;
        Node<T> next;
    
        public Node(T data) {
            this.data = data;
        }
    }
*/

public class Solution {
    public static Node<Integer> removeDuplicates(Node<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        Node<Integer> current = head;
        while (current.next != null) {
            if (current.data.equals(current.next.data)) {
                // 跳过重复的下一个节点
                current.next = current.next.next;
            } else {
                // 移动到下一个不同的节点
                current = current.next;
            }
        }
        return head;
    }
}

代码说明 #

• 从链表头节点开始遍历，用current指针跟踪当前处理的节点
• 当当前节点和下一个节点数据相同时，直接跳过下一个节点（修改next指针）
• 当数据不同时，移动current到下一个节点
• 全程只使用了一个额外指针，空间复杂度为O(1)，时间复杂度为O(n)（n为链表长度）

可选方案（不推荐） #

如果一定要保留递归写法，可以通过调整JVM启动参数增大栈空间（比如-Xss2m），但这种方法治标不治本，不同环境的栈限制不同，而且递归本身存在方法调用开销，大规模数据下性能不如迭代。

内容的提问来源于stack exchange，提问作者Aabid