1-4 删除链表中的元素

分数 7

作者 李廷元

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

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

函数接口定义：

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

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

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

裁判测试程序样例：

#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：

81 70 49 70 88 84 51 65 60 59
70

输出样例1：

81 49 88 84 51 65 60 59

输入样例2：

1
1

输出样例2：

NULL

解析

struct ListNode *removeElements(struct ListNode *head, int val) {
    struct ListNode * head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    head1->next = head;

    struct ListNode * prev = head1;
    struct ListNode * curr = head;

    while (curr != NULL) {
        if (curr->val == val) {
            prev->next = curr->next;
        }
        else {
            prev = curr;
        }
        curr = curr->next;
    }
    struct ListNode* newHead = head1->next;
    free(head1);
    return newHead;
}

注意

这段代码是用于删除链表中所有值等于val的节点的实现，核心思路是通过虚拟头节点（哨兵节点） 简化删除逻辑，配合双指针遍历完成操作。下面详细解释每一步的作用和整体逻辑：

1. 创建虚拟头节点（dummy node）

struct ListNode * head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
head1->next = head;

  • 作用：虚拟头节点是一个临时创建的节点，它的next指针指向原链表的头节点head。

  • 为什么需要它：

    原链表中，头节点的删除逻辑与其他节点不同（删除头节点时需要修改整个链表的头指针）。而虚拟头节点的存在可以

    统一所有节点的删除逻辑

    （包括头节点），避免单独处理头节点的复杂判断。

2. 定义双指针（prev 和 curr）

struct ListNode * prev = head1;  // 前驱指针：跟踪当前节点的前一个节点
struct ListNode * curr = head;   // 当前指针：遍历链表，检查节点是否需要删除
  • prev初始指向虚拟头节点，用于在删除节点时调整指针指向（跳过待删除节点）。
  • curr初始指向原链表的头节点，用于遍历所有节点并检查值是否为val。

3. 遍历链表并删除目标节点

while (curr != NULL) {  // 遍历所有节点，直到curr为NULL（链表结束）
    if (curr->val == val) {  // 当前节点需要删除
        prev->next = curr->next;  // 前驱节点直接跳过当前节点（删除curr）
    } else {  // 当前节点不需要删除
        prev = curr;  // 前驱节点后移到当前节点（保持跟踪关系）
    }
    curr = curr->next;  // 当前节点始终后移，继续遍历下一个节点
}

  • 循环逻辑

    ：从链表头开始，逐个检查每个节点的值：

    • 若curr的值等于val：说明curr是待删除节点，此时让prev->next直接指向curr->next（相当于跳过curr，完成删除）。
    • 若curr的值不等于val：说明curr需要保留，此时prev移动到curr的位置（因为下一个节点的前驱就是当前节点）。
    • 无论是否删除curr，curr都要后移（curr = curr->next），继续检查下一个节点。

4. 处理结果并释放内存

struct ListNode* newHead = head1->next;  // 虚拟头节点的next就是新链表的头节点
free(head1);  // 释放虚拟头节点的内存（避免内存泄漏）
return newHead;  // 返回删除后的链表头节点
  • 遍历结束后，虚拟头节点的next指针已经指向删除后的链表的第一个有效节点（可能是原链表的某个节点，也可能是NULL）。
  • 由于虚拟头节点是动态分配的（malloc），使用后必须通过free释放，否则会造成内存泄漏。

为什么这段代码能处理所有情况？

  1. 空链表：若原链表head为NULL，则head1->next为NULL，循环不执行，最终返回NULL，正确。
  2. 头节点需要删除：例如原链表为70->81，val=70。curr初始为70，满足删除条件，prev（此时是head1）的next会指向81，最终新头节点为81，正确。
  3. 连续多个节点需要删除：例如原链表为70->70->81，val=70。第一次curr是第一个70，删除后prev->next指向第二个70；第二次curr是第二个70，再次删除后prev->next指向81，最终保留81，正确。
  4. 尾节点需要删除：例如原链表为81->70，val=70。curr最后指向70，prev是81，prev->next会指向NULL，删除尾节点，正确。

总结

这段代码通过虚拟头节点统一了所有节点的删除逻辑，配合prev（前驱）和curr（当前）双指针高效遍历，能正确删除链表中所有值为val的节点，且处理了空链表、头节点删除、连续节点删除等所有边界情况，同时通过free释放了临时节点的内存，避免泄漏。