如何向升序链表中插入一个元素并保持有序?
哪些公司问过
答案要点
- 用哑节点 dummy 统一处理头部插入和空链表
- 循环条件为 cur.next 非空且 cur.next.val < val,停在插入位置的前驱
- 先 newNode.next = cur.next,再 cur.next = newNode,顺序不能颠倒
- 返回 dummy.next 作为新头节点,时间 O(n),空间 O(1)
易错点
- 不用哑节点时漏处理插在头部或空链表的情况
- 指针修改顺序颠倒,导致后续节点丢失
- 循环条件没判断 cur.next 是否为空,访问空指针
面试官常见追问
- 如果是循环有序链表怎么插?
- 双向链表插入要改哪些指针?
- 如果要插入很多元素,有更好的办法吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场