LeetCode 148题Sort List冒泡排序栈溢出问题排查

问题背景 #

使用递归版冒泡排序解决LeetCode 148. Sort List问题，本地Eclipse运行小规模测试用例正常，但提交到LeetCode平台时触发栈溢出错误。原代码如下：

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);
        }
    }
}

栈溢出原因 #

• 递归深度超出JVM栈上限：冒泡排序的递归次数等于链表长度n。LeetCode的测试用例包含长度上万的链表，而Java默认栈深度通常在1000左右，当n远大于这个值时，递归调用栈会被撑爆，触发StackOverflowError。
• 本地测试规模有限：本地运行的链表长度较短，递归深度未超过栈上限，因此未出现错误。

修复方法 #

将递归版冒泡排序改为迭代版，彻底规避递归栈溢出问题，同时优化原代码中反复遍历链表的低效操作。

迭代版冒泡排序实现 #

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        int size = size(head);
        // 外层循环控制排序轮数，每轮将最大元素移至未排序部分末尾
        for (int i = size - 1; i > 0; i--) {
            ListNode prev = null;
            ListNode curr = head;
            boolean swapped = false;
            // 内层循环遍历未排序区间，比较并交换相邻节点
            for (int j = 0; j < i; j++) {
                ListNode nextNode = curr.next;
                if (curr.val > nextNode.val) {
                    swapped = true;
                    // 处理交换逻辑
                    if (prev == null) {
                        // 交换头节点
                        curr.next = nextNode.next;
                        nextNode.next = curr;
                        head = nextNode;
                        prev = nextNode;
                    } else {
                        prev.next = nextNode;
                        curr.next = nextNode.next;
                        nextNode.next = curr;
                        prev = nextNode;
                    }
                } else {
                    prev = curr;
                    curr = nextNode;
                }
            }
            // 某轮无交换，说明链表已完全有序，提前终止
            if (!swapped) {
                break;
            }
        }
        return head;
    }

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

优化说明 #

• 加入swapped标志：若某一轮遍历未发生交换，直接终止排序，减少无效遍历。
• 避免重复遍历：迭代版在单次遍历中完成相邻节点的比较与交换，无需像原递归版那样反复调用point方法从头查找节点，提升了执行效率。

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