全方位解析：链表删除节点的多种方法与实战

链表是数据结构—尤其是面试与算法学习中的“常见宠儿”。删除节点作为链表操作的基础，却有多种思路：迭代、递归、双指针、双链表乃至循环链表。本文将一步步带你搞懂每种方法的原理、代码实现与应用场景，并配上直观图示，助力学生初学者快速上手。

1. 链表基础回顾

什么是链表？

• 链表是一种线性数据结构，由节点（val + next 指针）依次串联而成。
• 与数组不同，链表插入／删除不需要大规模搬移元素，时间复杂度可降至 O(1)。

典型节点结构（Java）：

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)

查看题目与更多案例 (CSDN)

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. 方法六：循环链表节点删除

循环链表最后一个节点指向头，删除要特别处理“最后”节点：

1. 遍历找到待删节点及其前驱。
2. 前驱的 next 指向待删的 next。
3. 若删除的是头节点，需更新外部 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 的算法笔记)

参考链接：

• CSDN 博客：总有适合你的方法去删除链表节点 (CSDN)
• LeetCode 19 删除链表倒数第 N 个节点 (CSDN)