6-183 Delete node from singly liked list

In this problem you will implement a function to delete the specified element in a singly linked list with dummy header.

Format of functions:

void removeNode(List L, ElementType e);

The parameter?L?is a pointer to the dummy header. The function delete the specified element?ein linked list L.

For the sake of simplicity, we assume that there are no duplicate elements in the linked list.(简单起见，我们约定链表中没有重复的元素)

where?List?is defined as the following:

typedef int ElementType; 
struct Node 
{ 
        ElementType data; 
        struct Node* next; 
}; 
typedef struct Node* PtrToNode; 
typedef PtrToNode List;

Sample program of judge:

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

typedef int ElementType;

struct Node
{
? ? ElementType data;
? ? struct Node* next;
};

typedef struct Node* PtrToNode;
typedef PtrToNode List;

void removeNode(List L, ElementType e);

void showList(List L);

int main(void)
{
? ? List L = malloc(sizeof(struct Node));
? ? L->next = NULL;

? ? ElementType x;
? ? scanf("%d", &x);
? ? while (x != -1)
? ? {
? ? ? ? PtrToNode t = malloc(sizeof (struct Node));
? ? ? ? t->data = x;
? ? ? ? t->next = L->next;
? ? ? ? L->next = t;
? ? ? ? scanf("%d", &x);
? ? }
? ? showList(L);
? ? ElementType e;
? ? scanf("%d", &e);
? ? removeNode(L, e);
? ? showList(L);
? ? return 0;
}

void showList(List L)
{
? ? PtrToNode p = L->next;
? ? if (p == NULL)
? ? {
? ? ? ? printf("NULL");
? ? ? ? return;
? ? }
? ? while (p != NULL)
? ? {
? ? ? ? printf("%d ", p->data);
? ? ? ? p = p->next;
? ? }
? ? printf("\n");
}

/* Your functions will be put here */

Sample Input 1:

2 27 32 1 5 -1
27

Sample Output 1:

5 1 32 27 2 
5 1 32 2 

Sample Input 2:

3 -1
3

Sample Output 2:

3 
NULL

Sample Input 3:

10 20 30 -1
15

Sample Output 3:

30 20 10 
30 20 10 

?

?void removeNode(List L, ElementType e)?
{
? ? List p=L->next;//p指针指向头结点的下一个节点即第一个节点
? ? List q=L;//q指针指向头结点
? ? while(p!=NULL){
? ? ? ? if(p->data==e){
? ? ? ? ? ? q->next=p->next;
? ? ? ? ? ? free(p);
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? q=p;//q指向当前p指向的位置
? ? ? ? p=p->next;//p往后移动
? ? }//保证了q总是指向p的前驱节点
}