AB14-删除带头结点单链表中所有值为x的结点

代码实现

/**
 * 删除带头结点单链表中所有值为x的结点
 * @param L 指向链表头结点的指针
 * @param x 要删除的目标值
 * @return 有结点被删除返回true，无结点被删除返回false
 */
bool Del(LinkList L, int x) {
    // r指向当前结点的前驱结点（从头结点开始）
    LinkList r = L;

    // 标记是否有结点被删除
    int flag = 0;

    // 遍历链表，查找并删除所有值为x的结点
    while (r->next != NULL) {
        // 如果下一个结点的值等于x
        if (r->next->data == x) {
            flag = 1;  // 标记有结点被删除

            // 准备删除操作
            LinkList p = r->next;  // p指向要删除的结点

            // 删除操作：绕过要删除的结点
            r->next = p->next;     // 前驱结点指向被删除结点的后继

            // 释放被删除结点的内存
            free(p);

            // 注意：这里不移动r指针，因为r->next已经指向了新的结点
            // 新的r->next可能仍然是x，需要继续检查
        } else {
            // 如果下一个结点不是要删除的结点，则移动r指针
            r = r->next;
        }
    }

    // 根据flag判断是否有结点被删除
    if (flag == 1) {
        return true;   // 有结点被删除
    } else {
        return false;  // 无结点被删除
    }
}

算法执行流程图解

删除过程示例：

链表：L→[ ]→[3]→[2]→[7]→[2]→[9]→[2]→[5]→NULL  删除x=2

执行过程：
r=L: r->next=[3], 3==2? 否 → r=[3]
r=[3]: r->next=[2], 2==2? 是 → 删除[2]
       r->next=[7], 7==2? 否 → r=[7] 
r=[7]: r->next=[2], 2==2? 是 → 删除[2]
       r->next=[9], 9==2? 否 → r=[9]
r=[9]: r->next=[2], 2==2? 是 → 删除[2]
       r->next=[5], 5==2? 否 → r=[5]
r=[5]: r->next=NULL, 结束

结果：L→[ ]→[3]→[7]→[9]→[5]→NULL

关键操作图解

连续删除的情况：

删除前：L→[ ]→[A]→[X]→[X]→[B]→NULL
              ↑    ↑    ↑
              r   r->next

第一次删除：
1. p = r->next = [X]
2. r->next = p->next = [X]  // r→[A]→[X]→[B]→NULL
3. free(p) = [X]

此时：L→[ ]→[A]→[X]→[B]→NULL
             ↑    ↑
             r   r->next

注意：r没有移动！继续检查新的r->next

复杂度分析

时间复杂度：O(n)

• 遍历时间：需要遍历整个链表一次，O(n)
• 删除时间：每次删除操作O(1)，最多删除n个结点，总计O(n)
• 总体时间复杂度：O(n)

空间复杂度：O(1)

• 额外空间：只使用了常数个指针变量：r、p、flag
• 内存释放：释放被删除结点的内存，不属于额外空间
• 算法额外空间复杂度：O(1)

算法优化版本

优化版本1：使用布尔值替代整数标记

/**
 * 优化版本1：使用布尔值替代整数标记
 */
bool Del_Optimized1(LinkList L, int x) {
    if (L == NULL) return false;

    LinkList r = L;
    bool deleted = false;  // 使用布尔值更清晰

    while (r->next != NULL) {
        if (r->next->data == x) {
            deleted = true;
            LinkList p = r->next;
            r->next = p->next;
            free(p);
            // 不移动r，继续检查新的r->next
        } else {
            r = r->next;
        }
    }

    return deleted;
}

优化版本2：返回删除的结点个数

/**
 * 优化版本2：返回删除的结点个数
 */
int Del_And_Count(LinkList L, int x) {
    if (L == NULL) return 0;

    LinkList r = L;
    int count = 0;

    while (r->next != NULL) {
        if (r->next->data == x) {
            LinkList p = r->next;
            r->next = p->next;
            free(p);
            count++;
            // 不移动r
        } else {
            r = r->next;
        }
    }

    return count;
}

与单个删除的对比

特征	删除第一个	删除所有
指针移动	找到后立即返回，移动r	找到后不移动r，继续检查
实现复杂度	相对简单	需要特别注意指针移动逻辑
时间复杂度	O(n)	O(n)
返回值	成功/失败	成功/失败

算法关键点总结

核心思想： - 遍历链表，删除所有值为x的结点 - 使用前驱指针技术，便于删除操作 - 关键是理解删除后不移动前驱指针的原因

重要细节： 1. 指针移动策略：删除时不移动r，不删除时才移动r 2. 内存管理：及时释放被删除结点的内存 3. 边界处理：正确处理空链表和连续相同值的情况

易错点： - 删除后忘记移动指针导致遗漏连续的相同值 - 删除后错误地移动指针导致逻辑错误 - 内存泄漏问题

这种算法在实际应用中很常见，比如清理链表中的特定数据或过滤操作。