有序数组二分查找与链表逆序输出
哪些公司问过
答案要点
- 二分查找用左闭右闭区间,l<=r 循环,mid=l+(r−l)/2 防溢出,O(log n)
- 区间更新为 mid+1 与 mid−1,否则可能死循环;有重复时用 lower_bound 找首个位置
- 链表逆序输出:递归后序打印,代码简洁但递归深度 O(n)
- 显式栈或原地三指针反转可避免深递归,反转法额外空间 O(1)
- 处理空数组、空链表、单节点等边界,链表各方法时间均为 O(n)
易错点
- mid 写成 (l+r)/2,下标很大时整数溢出
- 区间定义与循环条件不匹配,如左闭右开却写 r=mid−1,导致漏解或死循环
- 递归逆序输出超长链表导致栈溢出
面试官常见追问
- 三指针原地反转链表怎么写?
- 左闭右开区间的二分怎么写?
- 不能修改链表且内存紧张,怎么逆序输出?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。