PTA（链表）1-4 删除链表中的元素

1-4 删除链表中的元素

分数 7

作者 李廷元

单位 中国民用航空飞行学院

本题要求删除链表中等于给定值val的所有节点。链表ListNode的定义已经给出。要求给出函数removeElements的实现。

函数接口定义：

1
2
3
4
5
6
7
8
9
10
11
/*
* head为链表头指针；val为需要删除的值。
* 函数返回值为删除val后的链表的头指针。
*/
struct ListNode* removeElements(struct ListNode* head, int val);

/* 创建链表，细节不表 */
struct ListNode* buildList();

/* 打印链表，细节不表 */
void printList(struct ListNode* head);

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/**
 * Definition of ListNode
 */
struct ListNode
{
    int val;
    struct ListNode *next;
};

/*
* head为链表头指针；val为需要删除的值。
* 函数返回值为删除val后的链表的头指针。
*/
struct ListNode* removeElements(struct ListNode* head, int val);

/* 创建链表，细节不表 */
struct ListNode* buildList();

/* 打印链表，细节不表 */
void printList(struct ListNode* head);

int main()
{
    int val;
    struct ListNode* head = buildList();
    scanf("%d",&val);
    head = removeElements(head,val);
    printList(head);

    return 0;
}

/* 请在这里填写答案 */

输入样例1：

1
2
81 70 49 70 88 84 51 65 60 59
70

输出样例1：

1
81 49 88 84 51 65 60 59

输入样例2：

1
2
1
1

输出样例2：

1
NULL

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct ListNode* removeElements(struct ListNode* head, int val) {
    // 如果此时为空链表，返回NULL
    if (head == NULL) {
        return head;
    }
    // 先处理特殊情况：第一个结点是否要删除(可能有好几个)
    // while的第一个条件是怕只有一个元素val，执行一遍后，head指向空，再head->val会错
    while (head != NULL && head->val == val) {
        head = head->next;
    }
    // 如果此时为空链表，返回NULL
    if (head == NULL) {
        return head;
    }

    struct ListNode *p = head; // 用于遍历链表
    while (p->next != NULL) {
        if (p->next->val == val) {
            p->next = p->next->next;
        } else {
            // 无需删除，p后移
            p = p->next;
        }
    }
    return head;
}

采用 “分阶段处理” 策略，分两步删除目标节点：

  1. 处理头节点

    由于头节点没有前驱节点，删除头节点需要特殊处理：

    • 用while循环连续删除值为val的头节点（应对[2,2,2]删除2这类连续头节点场景）。

    • 每次删除后，头指针head后移（head = head->next）。

    • 循环条件

      1
      head != NULL && head->val == val

      确保：

      • 不会对空链表访问head->val（避免空指针错误）。
      • 只要头节点值为val就持续删除。

  2. 处理非头节点

    对于中间 / 尾部节点，通过前驱节点p进行删除：

    • 用p遍历链表，始终检查p->next（下一个节点）是否需要删除。
    • 若p->next->val == val，则跳过该节点（p->next = p->next->next）。
    • 若不需要删除，p正常后移（p = p->next）。

易错点分析

  1. 空指针访问风险
    • 错误场景：如果链表为空（head == NULL），直接访问head->val会导致崩溃。
    • 代码防护：开头的if (head == NULL) return head和while循环的head != NULL条件，避免了空指针访问。
  2. 连续头节点删除不彻底
    • 错误场景：若用if而非while处理头节点（如[1,1,2]删除1），只能删除第一个头节点，残留第二个1。
    • 代码防护：while循环确保所有连续的头节点都被删除。
  3. 删除后链表为空的处理
    • 错误场景：若删除所有节点后链表为空（如[1,1]删除1），后续操作p = head会导致p为空，访问p->next出错。
    • 代码防护：头节点处理后，再次检查if (head == NULL) return head，避免后续逻辑出错。
  4. 遍历终止条件错误
    • 错误场景：若用p != NULL作为循环条件（而非p->next != NULL），当p指向最后一个节点时，p->next为NULL，访问p->next->val会出错。
    • 代码防护：while (p->next != NULL)确保只检查到倒数第二个节点，避免访问NULL->val。
  5. 内存泄漏（隐性问题）
    • 代码缺陷：删除节点时未释放内存（free），虽然不影响编译运行，但长期会导致内存泄漏（尤其在频繁操作的场景中）。
    • 优化建议：删除节点前用临时指针保存，删除后释放（如struct ListNode* temp = head; head = head->next; free(temp);）。

这题没有头结点，会复杂

有头结点时，head 始终指向这个空的哨兵节点，所有数据节点都在 head->next 之后。删除逻辑统一为 “通过前驱节点删除目标节点”，无需分 “头节点 / 非头节点” 处理

  1. 无需单独处理原头节点

    原头节点（第一个数据节点）变成了 head->next，和其他数据节点一样有前驱（哨兵节点）。删除时直接通过 p->next 判断，不用写 while 循环单独处理连续的原头节点。

  2. 避免空指针访问风险

    哨兵节点始终存在（head 不会为空），无需在开头判断 “链表是否为空”，也不用在删除后检查 “链表是否变空”—— 即使所有数据节点都被删除，head 仍指向哨兵节点，head->next 自然为 NULL。

  3. 逻辑统一，代码更短

    所有删除操作都遵循 “找前驱→跳节点” 的统一逻辑，没有分支判断，可读性和维护性更强。