AB13-删除单链表中第一个值为x的结点

代码实现

/**
 * 删除单链表中第一个值为x的结点
 * @param L 指向链表头结点的指针
 * @param x 要删除的目标值
 * @return 删除成功返回true，未找到返回false
 */
bool del_x(LinkList L, int x) {
    // 边界条件检查：链表是否存在
    if (L == NULL) {
        return false;
    }

    // r指向当前结点，用于查找目标结点的前驱
    LNode* r = L;

    // 遍历链表查找目标结点
    while (r->next != NULL) {
        // 如果找到值为x的目标结点（r的后继结点）
        if (r->next->data == x) {
            // 执行删除操作
            LNode* p = r->next;      // p指向要删除的结点
            r->next = p->next;         // 跳过要删除的结点
            free(p);                   // 释放被删除结点的内存
            return true;               // 删除成功，返回true
        }
        r = r->next;  // 继续向后查找
    }

    // 遍历完整个链表都未找到目标结点，删除失败
    return false;
}

算法执行流程图解

删除过程示例：

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

查找过程：
r=L: r->next=[3], 3==2? 否 → r=[3]
r=[3]: r->next=[7], 7==2? 否 → r=[7]
r=[7]: r->next=[2], 2==2? 是 → 找到目标结点！

删除操作：
r=[7]  p=[2]  r->next=[9]

1. p = r->next;        → p指向要删除的[2]
2. r->next = p->next;  → [7]→[9]  (跳过[2])
3. free(p);            → 释放[2]的内存

删除后：L→[ ]→[3]→[7]→[9]→[2]→[5]→NULL

删除操作详细图解

删除前：L→[ ]→[A]→[B]→[C]→[D]→NULL
               ↑     ↑     ↑
               r    p(要删除) 

删除步骤：
步骤1：p = r->next
       L→[ ]→[A]→[B]→[C]→[D]→NULL
                    ↑
                    p

步骤2：r->next = p->next  
       L→[ ]→[A]→[C]→[D]→NULL
               ↑     ↑
               r    原来的[C]

       [B]→[C]→[D]→NULL  (原来的B结点被孤立)
            ↑
            p

步骤3：free(p)
       释放B结点的内存空间

复杂度分析

时间复杂度：O(n)

• 最好情况：O(1) - 目标结点在第一个位置
• 最坏情况：O(n) - 目标结点在最后一个位置或不存在
• 平均情况：O(n) - 平均需要查找n/2个结点
• 总体时间复杂度：O(n)

空间复杂度：O(1)

• 额外空间：只使用了常数个指针变量：r、p
• 算法额外空间复杂度：O(1)

算法变体：删除所有值为x的结点

/**
 * 删除单链表中所有值为x的结点
 * @param L 指向链表头结点的指针
 * @param x 要删除的目标值
 * @return 删除的结点个数
 */
int del_All(LinkList L, int x) {
    if (L == NULL) return 0;

    int count = 0;     // 记录删除的结点个数
    LinkList r = L;    // 前驱指针

    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;
}

递归版本实现

/**
 * 递归版本：删除第一个值为x的结点
 */
bool del_Recursive(LinkList L, int x) {
    if (L == NULL || L->next == NULL) {
        return false;
    }

    if (L->next->data == x) {
        // 找到目标结点，执行删除
        LinkList p = L->next;
        L->next = p->next;
        free(p);
        return true;
    }

    // 递归处理后续结点
    return del_Recursive(L->next, x);
}

算法特点

核心思想： 使用前驱指针遍历链表，当发现目标结点时，通过修改前驱结点的指针域来跳过目标结点，从而实现删除。

关键技巧： 1. 前驱指针法：使用r->next来访问当前结点，r作为前驱 2. 安全删除：先保存要删除的结点指针，再修改链接关系，最后释放内存

重要注意点： - 必须通过前驱结点来删除目标结点 - 删除后要及时释放内存，避免内存泄漏 - 正确处理未找到目标结点的情况

与顺序表删除的对比：

特性	顺序表	链表
查找时间	O(n)	O(n)
删除时间	O(n)	O(1)
空间复杂度	O(1)	O(1)
内存管理	无需释放	需要手动释放

链表的优势在于删除操作本身是O(1)的，但查找仍需O(n)时间。