[C语言/PTA] 单链表结点删除

题目要求

本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中所有存储了某给定值的结点删除。链表结点定义如下：

struct ListNode {
int data;
ListNode *next;
};
函数接口定义：
struct ListNode *readlist();
struct ListNode *deletem( struct ListNode *L, int m );
函数readlist从标准输入读入一系列正整数，按照读入顺序建立单链表。当读到−1时表示输入结束，函数应返回指向单链表头结点的指针。

函数deletem将单链表L中所有存储了m的结点删除。返回指向结果链表头结点的指针。

裁判测试程序样例：

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

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *readlist();
struct ListNode *deletem( struct ListNode *L, int m );
void printlist( struct ListNode *L )
{
     struct ListNode *p = L;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    int m;
    struct ListNode *L = readlist();
    scanf("%d", &m);
    L = deletem(L, m);
    printlist(L);

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：
10 11 10 12 10 -1
10

输出样例：
11 12

解题思路

结合所给代码，可分析代码实现过程如下：

通过 readlist() 函数将输入的数据存储到链表中，再调用 deletem() 函数来删除链表中指定的元素，最后通过 printlist() 函数输出最终的链表结果。

其中，struct ListNode 为链表节点结构体，包含两个成员变量：int data 表示当前节点存储的数据，struct ListNode *next 表示指向下一个节点的指针。

• 函数 void printlist(struct ListNode *L) 用于遍历整个链表并打印出每个节点的值；

• 函数 struct ListNode *readlist() 用于读取输入的数据并生成链表；

• 函数 struct ListNode *deletem(struct ListNode *L, int m) 用于删除链表中所有值为 m 的节点，并返回处理后的链表。

代码

struct ListNode *readlist()             // 读取链表
{
    struct ListNode *head,*p1,*p2;      // 定义头结点和两个临时指针变量
    int n=0;                            // 定义节点数量
    head = NULL;                        // 初始化头结点为空指针
    p1 = p2 = (struct ListNode*)malloc(sizeof(struct ListNode));  // 开辟新空间
    scanf("%d",&p1->data);              // 从键盘上读入第一个节点的数据
    while(p1->data!=-1)                 // 如果当前节点不是最后一个节点
    {
        n++;                            // 记录节点个数
        if(n==1)                        // 如果是头节点
            head = p1;                  // 将当前节点作为头结点
        else
            p2->next = p1;              // 将前一个节点指针指向当前节点

        p2 = p1;                        // 将 p1 赋值给 p2，以便在下一次循环中使用
        p1 = (struct ListNode*)malloc(sizeof(struct ListNode));   // 为下一节点开辟新空间
        scanf("%d",&p1->data);          // 读入下一个节点的数据
    }
    p2->next = NULL;                    // 最后一个节点指向 NULL
    return head;                        // 返回头结点指针
}

struct ListNode *deletem( struct ListNode *L, int m )    // 删除指定元素
{
    struct ListNode *p1,*p2;            // 定义两个指针变量
    p1 = L;                             // 将 L（链表的头结点）赋值给 p1
    while(p1!=NULL)                     // 循环遍历链表
    {
        if(p1->data==m)                 // 如果当前节点存储的数据等于待删除的数 m
        {
            if(p1==L)                   // 如果当前节点是头节点
                L = p1->next;           // 将头指针指向当前节点的下一个节点，即删除头节点
            else
                p2->next = p1->next;    // 将前一个节点的指针指向当前节点的下一个节点，即删除中间节点或尾节点
        }
        else
        {
            p2 = p1;                    // 将 p1 赋值给 p2，以便在下一次循环中使用
        }
        p1 = p1->next;                  // 将 p1 指向下一个节点
    }
    return L;                           // 返回操作后的链表
}

完整代码如下：

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

struct ListNode {
    int data;                           // 当前节点存储的数据
    struct ListNode *next;              // 指向下一个节点的指针
};

struct ListNode *readlist();             // 读取链表
struct ListNode *deletem( struct ListNode *L, int m );   // 删除指定元素
void printlist( struct ListNode *L )     // 输出链表
{
     struct ListNode *p = L;
     while (p) {                        // 循环遍历链表
           printf("%d ", p->data);      // 输出当前节点的数据
           p = p->next;                 // 寻找下一个节点
     }
     printf("\n");
}

int main()
{
    int m;                              // 定义待删除的数
    struct ListNode *L = readlist();    // 读取链表
    scanf("%d", &m);                    // 从键盘上输入待删除的数
    L = deletem(L, m);                  // 删除待删除的数并返回操作后的链表
    printlist(L);                       // 输出最终的链表

    return 0;
}

struct ListNode *readlist()             // 读取链表
{
    struct ListNode *head,*p1,*p2;      // 定义头结点和两个临时指针变量
    int n=0;                            // 定义节点数量
    head = NULL;                        // 初始化头结点为空指针
    p1 = p2 = (struct ListNode*)malloc(sizeof(struct ListNode));  // 开辟新空间
    scanf("%d",&p1->data);              // 从键盘上读入第一个节点的数据
    while(p1->data!=-1)                 // 如果当前节点不是最后一个节点
    {
        n++;                            // 记录节点个数
        if(n==1)                        // 如果是头节点
            head = p1;                  // 将当前节点作为头结点
        else
            p2->next = p1;              // 将前一个节点指针指向当前节点

        p2 = p1;                        // 将 p1 赋值给 p2，以便在下一次循环中使用
        p1 = (struct ListNode*)malloc(sizeof(struct ListNode));   // 为下一节点开辟新空间
        scanf("%d",&p1->data);          // 读入下一个节点的数据
    }
    p2->next = NULL;                    // 最后一个节点指向 NULL
    return head;                        // 返回头结点指针
}

struct ListNode *deletem( struct ListNode *L, int m )    // 删除指定元素
{
    struct ListNode *p1,*p2;            // 定义两个指针变量
    p1 = L;                             // 将 L（链表的头结点）赋值给 p1
    while(p1!=NULL)                     // 循环遍历链表
    {
        if(p1->data==m)                 // 如果当前节点存储的数据等于待删除的数 m
        {
            if(p1==L)                   // 如果当前节点是头节点
                L = p1->next;           // 将头指针指向当前节点的下一个节点，即删除头节点
            else
                p2->next = p1->next;    // 将前一个节点的指针指向当前节点的下一个节点，即删除中间节点或尾节点
        }
        else
        {
            p2 = p1;                    // 将 p1 赋值给 p2，以便在下一次循环中使用
        }
        p1 = p1->next;                  // 将 p1 指向下一个节点
    }
    return L;                           // 返回操作后的链表
}

总结

该题考察了链表的基本操作，包括链表的创建、遍历、删除指定元素等。
此外，还涉及到如何使用动态内存分配函数 malloc 和函数指针等知识点。

我是秋说，我们下次见。