第9课：链表的插入
进度 0/24
➕
链表的插入
指针一挥，新节点瞬间入列！
📖知识引入
🪄头插法
新节点next指向原头节点，head再指向新节点，两步完成插入
🎯按位置插入
先找到第i-1个节点（前驱），再让新节点接在它后面
⚠️先连后断
先把新节点连上后继，再让前驱指向新节点，顺序错了链就断
⚡O(1)插入
位置已定时，改两个指针就完成插入，无需挪动其他元素
💡
画图是链表debug神器：先画节点再画箭头，箭头一改对，代码自然对
🔍在p节点后面插入s
// 已有前驱节点 p 和新节点 s
Node* s = new Node{99, nullptr};
// 口诀：先连后断，顺序不能反
s->next = p->next; // 第1步：s先牵住p的后继
p->next = s; // 第2步：p改牵s
// 若先写 p->next = s，旧后继就失联了！两行代码完成插入，这正是链表的高光时刻
🎯小测验
第1题：在p之后插入s的正确顺序是？
第2题：头插法插入新节点后，新节点位于链表什么位置？
第3题：已知插入位置的前驱节点，链表插入的时间复杂度是？
📝本课知识点
- ✓先连后断是插入铁律
- ✓头插法两步上首位
- ✓定位前驱后插入是O(1)
第9课完成！继续探索下一课吧 🚀