本文解析为何在leetcode上用递归实现链表冒泡排序会触发栈溢出，而本地ide却正常运行，并提供规避递归深度爆炸的实用改进方案。
本文解析为何在leetcode上用递归实现链表冒泡排序会触发栈溢出，而本地ide却正常运行，并提供规避递归深度爆炸的实用改进方案。
LeetCode平台对内存与调用栈有严格限制，而你的bubbleSort方法采用双重递归结构（外层按轮次r递归，内层按位置c递归），导致总递归调用次数接近 $ O(n^2) $。当输入链表长度达到上限 $ n = 5 \times 10^4 $ 时，最坏情况下递归深度可达约 $ 2.5 \times 10^9 $ 层——远超JVM默认栈空间（通常仅支持数千至数万级递归），从而必然触发 StackOverflowError。相比之下，本地Eclipse测试往往使用小规模数据（如10–100节点），掩盖了该缺陷。
更关键的是，你的递归设计存在非尾递归+重复遍历问题：
- point(head, index) 每次都从头遍历链表定位节点，时间开销大；
- bubbleSort(..., r-1, 0) 和 bubbleSort(..., r, c+1) 均非尾递归，JVM无法优化为循环，每层调用均需压栈保存上下文；
- size(head) 在入口被调用一次，看似合理，但配合 $ O(n^2) $ 递归后，整体复杂度实际趋近 $ O(n^3) $。
✅ 正确解法方向（不改算法逻辑的前提下）：
1. 彻底消除递归 → 改用迭代实现冒泡排序
以下为安全、清晰的迭代版本（保留原逻辑语义，仅替换调用方式）：
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
int n = size(head);
// 外层：控制轮数（最多 n-1 轮）
for (int r = 0; r next.val) {
// 交换 curr 与 next
if (prev == null) {
// curr 是头节点
curr.next = next.next;
next.next = curr;
head = next;
} else {
prev.next = next;
curr.next = next.next;
next.next = curr;
}
// 交换后 prev 不变，curr 变为 next（因 next 已前移）
prev = next;
} else {
// 未交换：正常推进
prev = curr;
curr = next;
}
}
}
return head;
}
private int size(ListNode head) {
int count = 0;
while (head != null) {
count++;
head = head.next;
}
return count;
}
}
⚠️ 注意事项：
- 此迭代版时间复杂度仍为 $ O(n^2) $，仅解决栈溢出问题，不提升性能；
- LeetCode对该题的预期解是 $ O(n \log n) $ 时间 + $ O(1) $ 空间的自底向上归并排序（避免递归且稳定高效）；
- 若坚持练习排序思想，建议后续实现归并排序——它天然适配链表，递归深度仅为 $ \lceil \log_2 n \rceil \leq 16 $（对 $ n=5\times10^4 $），完全规避栈风险。
? 总结：栈溢出不是代码逻辑错误，而是算法复杂度与执行环境约束不匹配的典型表现。在算法题中，应始终将题目给定的数据范围作为设计起点——当 $ n $ 达 $ 10^4 $ 量级时，任何 $ O(n^2) $ 递归都应被警惕；优先选择迭代或更优算法，而非依赖“本地能跑通”。
