Remove the specified nodes in the linked list with dummy header

分数 20

作者 伍建全

单位 重庆科技大学

Please create a function with the prototype void removeNode(List L, int key). This function deletes all nodes from the linked list L where the data field is equal to key.If there are no nodes in the list where the data field is equal to key, the function should do nothing.

Structure description:

The node structure is shown below:

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

typedef node* position;
typedef position List;

Function definition:

void removeNode(List L, int key);

The parameter L is a pointer to the dummy header. This function deletes all nodes from the linked list L where the data field is equal to key. If there are no nodes in the list where the data field is equal to key, the function should do nothing.

Test program example：

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

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

typedef node* position;
typedef position List;

void removeNode(List L, int key);

// The questioner has implemented the createList function.
// This function reads a series of positive integers separated by spaces
// and inserts them into a linked list using the head insertion method.
// Entering -1 indicates the end of input.
// creatgeList函数由题目提供，不需要在本题的答案中实现
List createList();
//Function show outputs the data field of each node in the linked list L.
// show函数由题目提供，不需要在本题的答案中实现
void show(List L);
// destroy函数由题目提供，不需要在本题的答案中实现
void destroy(List L);

int main(void)
{
    List L = createList();
    show(L);
    int key;
    scanf("%d", &key);
    removeNode(L, key);
    show(L);
    destroy(L);
    return 0;
}

Input Specification:

There are two lines of input. The first line is a series of positive integers, and entering -1 indicates the end of the input. The second line contains one integer, which represents the number that needs to be deleted from the linked list.(输入有两行。第1行是一系列正整数，输入-1表示输入结束。第2行有1个整数，表示需要从链表中删除的数。)

Output Specification:

There are two lines of output. The first line is the linked list before the element is deleted; the second line is the linked list after the deletion.

Sample Input :

10 20 30 40 50 40  40 60 -1
40

Sample Output :

60 40 40 50 40 30 20 10 
60 50 30 20 10 

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

C程序如下：

// 定义一个函数，用于从链表中删除具有特定键值的节点  
void removeNode(List L, int key){  
    // 定义两个指向节点的指针，p和q  
    node *p, *q;  
    // 将p指向链表的头节点  
    p = L;  
    // 将q指向头节点的下一个节点，即链表的第一个实际数据节点  
    q = p->next;  
    // 当q不为NULL时，即链表中还有节点时，循环继续  
    while(q != NULL){  
        // 如果q所指向的节点的数据等于要删除的键值  
        if(q->data == key){  
            // 将p的next指针指向q的下一个节点，从而跳过q节点  
            p->next = q->next;  
            // 释放q节点所占用的内存  
            free(q);  
            // 将q重新指向p的下一个节点，继续检查下一个节点  
            q = p->next;  
        }  
        // 如果q所指向的节点的数据不等于要删除的键值  
        else{  
            // 将p移动到q的位置，即p指向当前检查的节点  
            p = q;  
            // 将q移动到下一个节点，准备检查下一个节点  
            q = q->next;  
        }  
    }  
}