全方位解析：链表删除节点的多种方法与实战
温馨提示：
本文最后更新于 2025年07月20日，已超过 6 天没有更新。若文章内的图片失效（无法正常加载），请留言反馈或直接联系我。
链表是数据结构—尤其是面试与算法学习中的“常见宠儿”。删除节点作为链表操作的基础，却有多种思路：迭代、递归、双指针、双链表乃至循环链表。本文将一步步带你搞懂每种方法的原理、代码实现与应用场景，并配上直观图示，助力学生初学者快速上手。
1. 链表基础回顾
什么是链表？
- 链表是一种线性数据结构，由节点（
val+next指针）依次串联而成。 - 与数组不同，链表插入／删除不需要大规模搬移元素，时间复杂度可降至 O(1)。
典型节点结构（Java）：
class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
2. 方法一：带哨兵节点的迭代删除
思路：先创建「虚拟头节点」（dummy），简化头部删除的特殊处理；通过一个指针 cur 遍历，遇到目标值就跳过，否则继续前进。
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null) {
if (cur.next.val == val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return dummy.next;
- 时间复杂度：O(n)
- 空间复杂度：O(1)
3. 方法二：递归法删除
思路：递归地处理子链表，再判断当前头节点是否需要被删除。
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
- 时间复杂度：O(n)
- 空间复杂度：O(n)（递归栈）
4. 方法三：原链表暴力删除
思路：先处理所有头部连续待删节点，再像方法一那样遍历中间节点。
while (head != null && head.val == val) {
head = head.next;
}
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.next.val == val) cur.next = cur.next.next;
else cur = cur.next;
}
return head;
- 适用场景：简单易懂，但需分两步处理头部与中部。
- 复杂度：同迭代法。
5. 方法四：双指针删除倒数第 N 个节点
对应 LeetCode 19 题，经常面试考察。
核心：快指针先走 N+1 步，随后快慢指针齐头并进，当快指针到末尾时，慢指针正好在待删节点前。
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
for (int i = 0; i <= n; i++) fast = fast.next;
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
- 时间复杂度：O(n)
- 空间复杂度：O(1)
6. 方法五：双链表节点删除
双链表节点含有 prev 和 next 指针，删除更为简单：
if (node == null) return;
node.prev.next = node.next;
if (node.next != null) node.next.prev = node.prev;
- 只需 O(1) 时间，无需遍历。
- 适用于已知待删节点地址的场景（如 LRU Cache）。
alt：双链表删除节点前后指针更新
7. 方法六：循环链表节点删除
循环链表最后一个节点指向头，删除要特别处理“最后”节点：
- 遍历找到待删节点及其前驱。
- 前驱的
next指向待删的next。 - 若删除的是头节点，需更新外部
head引用。
ListNode prev = head;
while (prev.next != head && prev.next.val != val) {
prev = prev.next;
}
if (prev.next.val == val) {
if (prev.next == head) head = head.next;
prev.next = prev.next.next;
}
return head;
- 注意：要处理空链表或仅剩单节点的情况。
8. 总结与最佳实践
- 优先选：带哨兵的迭代方法，代码简洁、边界统一；
- 递归：思路优雅，但栈深度受限；
- 双指针：倒数第 N 个节点删除必备；
- 双/循环链表：指针更多，删除更灵活。
掌握这些基本思路后，你可以应对绝大多数链表删除场景。
更深入的可视化演示与练习，请参见：Labuladong 算法可视化 (labuladong 的算法笔记)
参考链接：
正文到此结束
- 本文标签： 链表 删除节点 Java
- 本文链接： https://code.itptg.com/article/72
- 版权声明： 本文由老魏原创发布，转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
