Lesson 31: 单链表查找与删除

练习任务

难度：中

在 Lesson 30 构建链表的基础上，实现单链表的三种核心操作：

1. find_by_value(head, val) — 按值查找：返回第一个 data == val 的节点指针，未找到返回 NULL。
2. find_by_index(head, idx) — 按索引查找（0-based）：返回第 idx 个节点指针，越界返回 NULL。
3. delete_node(head, val) — 按值删除：删除第一个匹配节点，返回可能已更新的 head。

make_node、build_list、list_print、list_free 已提供。

本课共有 6 组测试用例：

输入 "1 2 3 4\nfind 3\n"    → 输出 "found: 3"
输入 "1 2 3 4\nfind 5\n"    → 输出 "not found"
输入 "1 2 3 4\nindex 2\n"   → 输出 "at 2: 3"
输入 "1 2 3\nindex 5\n"     → 输出 "out of range"
输入 "1 2 3\ndelete 2\n"    → 输出 "1 3"
输入 "1\ndelete 1\n"        → 输出 "(empty)"

提示：查找很简单——只需遍历比较。删除是难点——必须维护前驱指针 prev，因为单链表的节点无法“回看”前一个节点。你需要用 prev->next = cur->next 来“跳过”被删除的节点。

---

核心知识点

• 只读遍历（查找用）：单指针 cur 逐步前进，比较或计数
• 带前驱指针遍历（删除需要！）：prev 滞后 cur 一步，这是删除操作的基石
• 删除五种情形：头节点、中间节点、尾节点、唯一节点、未找到
• free 顺序：先改指针，再 free——顺序不能反
• 情形判断标志：prev == NULL（删头） + cur->next == NULL（删尾）
• 单链表删除为何比插入难：插入只需知道位置，删除需要知道前一个节点
• 双向链表：每个节点有 prev 指针，任何位置删除都是 O(1)
• 删除所有匹配项：先保存 cur->next 再 free(cur)，否则访问已释放内存

---

代码框架

31_singly_list_modify.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node { int data; struct node *next; };
struct node *make_node(int val) {
    struct node *p = malloc(sizeof(*p));
    p->data = val; p->next = NULL; return p;
}
struct node *build_list(char *nums) {
    struct node *head = NULL, *tail = NULL;
    char *tok = strtok(nums, " ");
    while (tok) {
        struct node *p = make_node(atoi(tok));
        if (!head) head = tail = p;
        else { tail->next = p; tail = p; }
        tok = strtok(NULL, " ");
    }
    return head;
}
void list_print(struct node *head) {
    if (!head) { printf("(empty)\n"); return; }
    struct node *p = head;
    while (p) { printf("%d", p->data); p = p->next; if (p) printf(" "); }
    printf("\n");
}
void list_free(struct node *head) {
    while (head) { struct node *next = head->next; free(head); head = next; }
}

/* 按值查找 */
struct node *find_by_value(struct node *head, int val) {
    // 遍历链表，比较 data == val
    // 找到返回节点指针，未找到返回 NULL
}

/* 按索引查找（0-based） */
struct node *find_by_index(struct node *head, int idx) {
    // 遍历计数，到达 idx 时返回节点指针
    // 越界返回 NULL
}

/* 按值删除 */
struct node *delete_node(struct node *head, int val) {
    // 维护 prev 和 cur 两个指针
    // 区分五种情形：头/中/尾/独/未找到
    // 先改指针，再 free
    // 返回可能已更新的 head
}

int main(void) {
    char nums[256], cmd[256];
    fgets(nums, sizeof(nums), stdin); fgets(cmd, sizeof(cmd), stdin);
    for (int i = 0; nums[i]; i++) if (nums[i] == '\n') nums[i] = '\0';
    for (int i = 0; cmd[i]; i++) if (cmd[i] == '\n') cmd[i] = '\0';
    char nums_copy[256]; strcpy(nums_copy, nums);
    struct node *head = build_list(nums_copy);
    char op[16]; int val; sscanf(cmd, "%s %d", op, &val);
    // 根据 op 分发: find/index/delete
    list_free(head); return 0;
}

TIP

先不要往下翻看参考解答。特别注意 delete_node 中 prev 的初始化与更新时机——这是大多数 bug 的源头。

---

深度讲解

1. 链表遍历的两种模式

查找和删除对链表遍历的要求完全不同。

模式 A：只读遍历（查找用）

struct node *cur = head;
while (cur != NULL) {
    // 处理 cur->data
    cur = cur->next;
}

只需一个指针 cur，从头到尾滑动。每轮只读不写。

模式 B：带前驱指针遍历（删除需要！）

struct node *prev = NULL;
struct node *cur = head;
while (cur != NULL) {
    if (/* 找到目标 */) {
        // 用 prev 和 cur 执行删除
    }
    prev = cur;        // ← 关键！prev 落后 cur 一步
    cur = cur->next;
}

prev 始终指向 cur 的前一个节点。这个“滞后一步”的关系是删除操作正确性的基石。

遍历过程中 prev 和 cur 的关系:

  初始:  prev=NULL  cur=head
  第一轮:  prev=head  cur=head->next
  第二轮:  prev=head->next  cur=head->next->next
  ...

2. 按值查找 find_by_value

遍历链表，逐一比较每个节点的 data，找到第一个匹配即返回。

链表: [1]→[3]→[5]→[7]→NULL  查找 val=5

cur=1: 1 != 5 → cur=cur->next
cur=3: 3 != 5 → cur=cur->next
cur=5: 5 == 5 → 返回指向此节点的指针

查找 val=9:
cur=1→3→5→7→NULL (遍历结束)
未找到 → 返回 NULL

3. 按索引查找 find_by_index

遍历时维护计数器 i，当 i == idx 时返回当前节点。

链表: [A]→[B]→[C]→[D]→NULL  查找 idx=2

i=0 cur=A: 0!=2 → i=1 cur=B
i=1 cur=B: 1!=2 → i=2 cur=C
i=2 cur=C: 2==2 → 返回 C

查找 idx=5:
遍历到尾，最大索引 3，5>3 → 返回 NULL (越界)

4. 删除操作 delete_node — 五种边界

删除是链表操作中最容易出错的部分。必须区分五种情况：

#	情况	prev	操作	head 变化
1	删头节点	NULL	head=cur->next; free(cur)	更新为新 head
2	删中间节点	!=NULL	prev->next=cur->next; free(cur)	不变
3	删尾节点	!=NULL, cur->next==NULL	prev->next=NULL; free(cur)	不变
4	删唯一节点	NULL, cur->next==NULL	free(cur)	变为 NULL
5	未找到	—	不操作	不变

情形判断标志：

• prev == NULL ⇔ 正在删除头节点（或唯一节点）
• cur->next == NULL ⇔ 正在删除尾节点（或唯一节点）

5. free 的顺序：先改指针，再 free

// 正确顺序:
prev->next = cur->next;   // 先调整指针，跳过 cur
free(cur);                // 再释放 cur

// 错误顺序:
free(cur);                // 先释放！
prev->next = cur->next;   // cur 已释放，访问 cur->next = 未定义行为！

CAUTION

一旦 free(cur)，cur 指向的内存就不再属于你。任何对 cur->next 的访问都是 Use-After-Free，行为未定义。

6. 为什么单链表删除比插入难？

插入只需知道“在哪里插”：

• 头插：直接改 head，O(1)
• 尾插：找到尾节点并挂上去，O(n)

删除需要知道“被删节点的前一个”：

• 单链表的节点只有 next 指针，无法“回看”前一个节点
• 必须通过遍历维护 prev 指针才能知道前一个是谁

插入 vs 删除的指针操作对比:

插入: 只操作新节点 + 目标位置
  p->next = head;
  head = p;  // 完成

删除: 需操作前一个节点 + 被删节点 + 后一个节点
  prev->next = cur->next;   // 前一个 跳过 被删节点，指向后一个
  free(cur);                // 释放被删节点

7. 双向链表：任何位置删除都是 O(1)

struct dnode { int data; struct dnode *prev; struct dnode *next; };

void delete_dnode(struct dnode *cur) {
    if (cur->prev) cur->prev->next = cur->next;
    if (cur->next) cur->next->prev = cur->prev;
    free(cur);
    // O(1)! 不需要遍历找前驱！
}

双向链表的每个节点知道自己的前一个是谁，因此任何位置的删除都是 O(1)。代价是每个节点多占 8 字节（prev 指针）。

8. 删除所有匹配项

struct node *delete_all(struct node *head, int val) {
    struct node dummy = {0, head};  // 哨兵节点，统一处理
    struct node *prev = &dummy;
    struct node *cur = head;
    while (cur) {
        if (cur->data == val) {
            prev->next = cur->next;
            struct node *tmp = cur;   // 先保存！
            cur = cur->next;          // 前进
            free(tmp);                // 再释放
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    return dummy.next;
}

TIP

删除后先用临时变量保存 cur，先让 cur 前进，再 free 临时变量。这样避免了访问已释放内存的问题。

---

参考解答

练习: find_by_value, find_by_index, delete_node 完整实现

solution_31_singly_list_modify.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node { int data; struct node *next; };
struct node *make_node(int val) {
    struct node *p = malloc(sizeof(*p));
    p->data = val; p->next = NULL; return p;
}
struct node *build_list(char *nums) {
    struct node *head = NULL, *tail = NULL;
    char *tok = strtok(nums, " ");
    while (tok) {
        struct node *p = make_node(atoi(tok));
        if (!head) head = tail = p;
        else { tail->next = p; tail = p; }
        tok = strtok(NULL, " ");
    }
    return head;
}
void list_print(struct node *head) {
    if (!head) { printf("(empty)\n"); return; }
    struct node *p = head;
    while (p) { printf("%d", p->data); p = p->next; if (p) printf(" "); }
    printf("\n");
}
void list_free(struct node *head) {
    while (head) { struct node *next = head->next; free(head); head = next; }
}

struct node *find_by_value(struct node *head, int val) {
    struct node *cur = head;
    while (cur) {
        if (cur->data == val) return cur;
        cur = cur->next;
    }
    return NULL;
}

struct node *find_by_index(struct node *head, int idx) {
    struct node *cur = head;
    int i = 0;
    while (cur) {
        if (i == idx) return cur;
        i++;
        cur = cur->next;
    }
    return NULL;
}

struct node *delete_node(struct node *head, int val) {
    if (!head) return NULL;
    /* 删头节点 */
    if (head->data == val) {
        struct node *new_head = head->next;
        free(head);
        return new_head;
    }
    /* 删中间或尾部 */
    struct node *prev = head;
    struct node *cur = head->next;
    while (cur) {
        if (cur->data == val) {
            prev->next = cur->next;  /* 先改指针 */
            free(cur);               /* 再释放 */
            return head;
        }
        prev = cur;
        cur = cur->next;
    }
    return head;  /* 未找到 */
}

int main(void) {
    char nums[256], cmd[256];
    fgets(nums, sizeof(nums), stdin);
    fgets(cmd, sizeof(cmd), stdin);
    for (int i = 0; nums[i]; i++) if (nums[i] == '\n') nums[i] = '\0';
    for (int i = 0; cmd[i]; i++) if (cmd[i] == '\n') cmd[i] = '\0';
    char nums_copy[256];
    strcpy(nums_copy, nums);
    struct node *head = build_list(nums_copy);
    char op[16]; int val;
    sscanf(cmd, "%s %d", op, &val);
    if (strcmp(op, "find") == 0) {
        struct node *r = find_by_value(head, val);
        if (r) printf("found: %d\n", r->data);
        else printf("not found\n");
    } else if (strcmp(op, "index") == 0) {
        struct node *r = find_by_index(head, val);
        if (r) printf("at %d: %d\n", val, r->data);
        else printf("out of range\n");
    } else if (strcmp(op, "delete") == 0) {
        head = delete_node(head, val);
    }
    list_print(head);
    list_free(head);
    return 0;
}

关于实现方式的说明：上述参考解答采用「先判头节点 + 后遍历内部节点」的两阶段方案（prev=head, cur=head->next），与正文§4 中 prev=NULL, cur=head 统一遍历的五情形分析是两套等价写法。两阶段写法将「删头」作为特例提前处理，避免了在遍历循环内判 prev==NULL 的重复判断，代码更简洁、性能略优；五情形写法则更直观地反映删除的边界分类，便于初学记忆。两种写法互相映照——建议先掌握五情形统一遍历，理解后再用两阶段精简优化。

---

课堂讨论

1. find_by_value 和 find_by_index 的遍历模式有何区别？各自在什么情况下结束遍历？
2. delete_node 中，为什么不能先 free(cur) 再 prev->next = cur->next？举例说明后果。
3. 如果链表是双向链表（有 prev 指针），删除会简化吗？为什么？
4. 如果要删除所有值为 val 的节点而不是只删第一个，算法需要如何调整？
5. 为什么 delete_node 要返回 struct node *？用传二级指针能解决吗？

讨论答案

Q1: 两种查找的遍历模式区别

find_by_value: 比较 data 字段，找到即返回。结束条件：匹配成功或 cur==NULL。 find_by_index: 维护计数器 i，当 i==idx 时返回。结束条件：i==idx 或 cur==NULL。

Q2: 为什么不能先 free 再改指针

因为 free(cur) 后，cur->next 的内存已经不属于你。访问已 release 的内存是 Use-After-Free，行为未定义。可能立即崩溃，也可能偷偷产生错误结果。

Q3: 双向链表的删除简化

会。双向链表每个节点知道自己的前一个是谁，因此任何位置的删除都是 O(1)，不需要遍历找前驱。

Q4: 删除所有匹配项

遍历整个链表，每找到一个就删除。关键是删除后 cur 已失效，需要用临时变量保存 next 再继续。使用哨兵节点可以统一删头和删中间的处理。

Q5: 为什么返回 struct node *

与 Lesson 30 相同的原因：C 语言按值传递。删头节点时 head 会改变，必须通过返回值传递新 head。传二级指针 void delete_node(struct node **head, int val) 也可以，但不如返回值直观。

---

课后练习

1. 统计匹配次数: 实现 count_matches(head, val)，遍历链表统计 data == val 的节点数。
2. 查找最后一个匹配: 实现 find_last(head, val)，返回最后一个 data == val 的节点指针。
3. 删除所有匹配项: 实现 delete_all(head, val)，删除链表中所有 data == val 的节点。
4. 逆序查找: 设计算法找到链表的倒数第 k 个节点（用双指针）。

---

参考资料

• K&R《C程序设计语言》§6.7 — 链表实现
• 《数据结构与算法分析》§3.2 — 链表 ADT
• man free — 内存释放
• Linux Kernel list.h — 双向链表实现

"The computing scientist's main challenge is not to get confused by the complexities of his own making." -- E. Dijkstra