C 语言第80题：单链表：删除值为 x 的节点

题目

单链表：删除值为 x 的节点

思路

本题在单链表中删除值为 x 的节点。

特判头节点：若头元素等于 x 则更新 head。否则用 prev 跟踪前驱，找到 cur->v==x 时让 prev->next=cur->next 并 free(cur)。

解题分析

删第一个值为 x 的节点：找前驱 p 使 p->next->v==x，p->next=p->next->next，别 free 后仍访问。虚拟头结点 dummy 可统一删头节点的情况。

完整程序

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

struct Node {
    int v;
    struct Node *next;
};

int main(void)
{
    int n, x, v;
    struct Node dummy = {0, NULL}, *tail = &dummy;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &v);
        struct Node *p = malloc(sizeof *p);
        p->v = v;
        p->next = NULL;
        tail->next = p;
        tail = p;
    }
    scanf("%d", &x);
    struct Node *p = &dummy;
    while (p->next && p->next->v != x) {
        p = p->next;
    }
    if (p->next) {
        struct Node *del = p->next;
        p->next = del->next;
        free(del);
    }
    for (p = dummy.next; p; p = p->next) {
        printf("%d ", p->v);
    }
    putchar('\n');
    return 0;
}

运行示例

输入：

4
1 2 3 2
2

输出：

1 3 2