链表算法题常见解题方法总结（面试高频模板）
前言
数组题考察的是下标操作，而链表题考察的核心永远是指针操作。
很多同学刷链表的时候会发现：
- 题目千变万化；
- 解法却总是在重复。
因为链表题真正高频的方法只有几个：
- 哨兵节点（Dummy Node）
- 快慢指针（Fast & Slow Pointer）
- 指针反转
- 双指针遍历
- 递归
- 分治
掌握这些技巧，大部分链表题都能快速找到思路。
一、哨兵节点（Dummy Node）
核心思想
在原链表前面人为增加一个虚拟节点。
dummy -> 1 -> 2 -> 3代码：
dummy=ListNode(0,head)为什么需要？
因为头节点比较特殊。
例如：
删除节点2：
1 -> 2 -> 3可以直接：
pre.next=pre.next.next但是删除节点1：
1 -> 2 -> 3需要：
head=head.next逻辑完全不同。
加入 dummy 后：
dummy -> 1 -> 2 -> 3删除任何节点：
pre.next=pre.next.next全部统一处理。
高频题目
- 删除链表的倒数第 N 个节点
- 两两交换链表中的节点
- 移除链表元素
- 反转链表 II
- 合并两个有序链表
使用模板
dummy=ListNode(0,head)cur=dummyreturndummy.next二、快慢指针（Fast & Slow Pointer）
核心思想
两个指针速度不同：
slow=slow.nextfast=fast.next.next利用速度差解决问题。
应用一：寻找链表中点
whilefastandfast.next:slow=slow.nextfast=fast.next.next当循环结束：
slow就在链表中间。
应用二：删除倒数第 N 个节点
先让：
fast走 N 步。
然后：
fast slow一起走。
当：
fast到达末尾：
slow刚好位于待删除节点的前驱。
应用三：判断链表有环
如果存在环：
快指针一定会追上慢指针。应用四：寻找环的入口
第一次相遇后：
p=head然后：
p=p.nextslow=slow.next再次相遇的位置就是环入口。
三、指针反转
核心思想
改变 next 指向。
模板
pre=Nonecur=headwhilecur:nxt=cur.nextcur.next=pre pre=cur cur=nxtreturnpre高频题目
- 反转链表
- 反转链表 II
- K 个一组翻转链表
- 回文链表
四、递归思想
核心思想
先处理子问题，再处理当前节点。
模板
defdfs(node):ifnotnode:returndfs(node.next)高频题目
- 反转链表
- 合并链表
- 排序链表
五、分治思想
核心思想
把链表拆成两部分处理。
高频题目
- 排序链表
- 合并 K 个升序链表
六、链表题万能思考顺序
做题时先问自己：
第一步
能不能加 Dummy？
第二步
能不能用快慢指针？
第三步
能不能反转？
第四步
能不能递归？
第五步
能不能分治？
总结
链表题虽然题目很多，但真正高频的方法只有几个：
- 哨兵节点
- 快慢指针
- 指针反转
- 递归
- 分治
掌握这些模板之后，大部分链表题都能快速找到突破口。
