我的 LeetCode 问题解决方案给出了堆栈溢出错误，但在我的 Eclipse IDE 上运行良好

Question

我正在尝试解决 LeetCode 问题 148。使用冒泡排序对 List 进行排序，但我在平台上的解决方案中遇到堆栈溢出错误，而它在我的 Eclipse IDE 上运行良好。为什么会这样以及如何解决？ 这是代码（Java）-

class Solution {
    public ListNode sortList(ListNode head) {
        return bubbleSort(head,size(head)-1,0);
    }

    int size(ListNode head){
        int c=0;
        while(head!=null){
            c++;
            head=head.next;
        }
        return c;
    }

    ListNode point(ListNode head,int index){
        for(int i=0;i<index;i++){
            head=head.next;
        }
        return head;
    }

    public ListNode bubbleSort(ListNode head,int r,int c){
        if(r==0){
            return head;
        }
        if(c<r){
            ListNode first = point(head,c);
            ListNode second = point(head,c+1);
            if(first.val > second.val){
                if(first==head){
                    first.next=second.next;
                    second.next=first;
                    head=second;
                }else{
                    ListNode prev=point(head,c-1);
                    prev.next=second;
                    first.next=second.next;
                    second.next=first;
                }
            }
            return bubbleSort(head,r,c+1);
        }else{
            return bubbleSort(head,r-1,0);
        }
    }
}

Ps：我知道问题的更好解决方案是通过合并排序，但我想知道我在这里的错误。

Answer 1

您可能已经知道，堆栈溢出错误的最常见原因之一是在函数中递归得太深。计算机的堆栈大小有限，无法跟踪嵌套函数调用，一旦达到该限制，它就会失败。

最有可能发生的事情是你用短列表测试了你的代码，因为你的代码逻辑是正确的，所以它工作得很好。但是，冒泡排序是一种 O(n^2) 算法，并且由于您实现它的方式，这意味着您的函数可以递归 n^2 倍的输入列表长度。在你链接到的 LeetCode 问题中，它说

链表的节点数在[0, 5 * 10^4]范围内。

当竞争性编程站点给出这样的约束范围时，您几乎可以肯定他们会测试范围的底部、范围的顶部以及中间的几个值。您的函数适用于较小的列表长度，但是当它传递一个 5*10^4 (50,000) 个节点长的列表时，它将尝试在 50,000^2 = 25 亿次的范围内递归，这将远远超过堆栈任何典型计算机的空间。

相比之下，归并排序的递归深度是 log(n)，这意味着即使 LeetCode 给你的最大可能输入，它也只会递归 16 次。或者，您可以重构您的算法以使用迭代而不是递归，这将通过根本不递归来完全回避问题。 （执行起来需要很长时间！）

希望这有帮助！