算法刷题模型整理（一）

模板

解题模型：

核心思路：

易错点：

链表

常见问题：

1. dummy节点的作用

1. 提供一个稳定的前驱节点
2. 统一头节点和普通节点的处理逻辑
3. 只是一个常数级额外节点，不会影响空间复杂度

2.

LC203 删除链表元素

解题模型：
迭代

核心思路：
检查p->next是否命中，命中则删除，p->next = p->next->next

易错点：

• 需设立哑节点dummy，否则会漏过head
• 边界条件p和p->next都不能为nullptr
• 删除时不能用if检查，而是要用while，否则连续命中时会漏
• 结束时要记得回收dummy内存

LC206 反转链表

解题模型：

​ 迭代，三指针

核心思路：

​ pre指向前一个，cur指向当前节点，next保存cur->next，将cur->next指向pre，然后后移pre与cur进行迭代

易错点：

• 指针的初始化，pre初始化为nullptr，cur指向head

• 边界条件为cur!=nullptr

*初见思路：设置哑节点，迭代链表，头插法

LC024 两两交换链表中的节点

解题模型：

​ 迭代，三指针

核心思路：

​ 三指针，cur迭代链表，交换cur和cur->next，pre保存cur前一个节点，next保存cur->next->next

易错点：

• 边界条件，cur为nullptr或cur->next为nullptr，即剩余节点不足两个时就停止
• 交换时每一步指针操作的顺序

LC019 删除链表的倒数第N个节点

解题模型：

​ 快慢指针

核心思路：

​ 快指针是慢指针前面第N个节点，两个指针同时后移，直到快指针走到最后一个节点，此时慢指针即为倒数第N+1个节点

易错点：

• 设置哑节点
• 要找的是目标节点的前一个节点，这样才能删除
• 快慢指针的关系，循环终止条件

LC142 环形链表II

解题模型：

​ 双指针，数学推导

核心思路：

​ Floyd Cycle Detection

​ 先快慢指针从head出发，到达相遇点后，一个指针从head出发，另一个从相遇点出发，新的相遇点即为入环点

易错点：

• 不太用dummy，没什么大用处
• 分两个阶段，找了两次相遇点

数组

常见问题：

1. 滑动窗口的使用时机
2. 要求连续子区间
3. 单调性，右边扩大时朝一个方向变化，左边缩小时朝反方向变化