习题11-8 单链表结点删除 (20 分)

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

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 

结尾无空行

思路：还是根据我们判断的顺序，第一个输入样例中，我们首先得判断自己建立的链表是否是m，如果是的话，我们就需要去掉他，最简单的方法就是头指针指向结构里面的next，也就到达了下一个链表，此时我们就用个循环，直到L->next=NULL,，为什么不是L=NULL呢，在调试的过程中，我发现如果建立的链表如果有5个，但是你的第五个还有p->next,就会报错，就是啥也不给你输出。紧接着，我们到达了第一个不是m值的链表，按照我们的思路就是一眼看到不是m值的那一个位置，我们希望计算机也是这样，如果下一个位置是m的话，我们就让这个链表的next先什么也不指，也就是NULL，如果是不是m的话，那么我们就让该链表的头部和上一个链表的尾部连接起来。据此思路，我们写了如下的代码。

struct ListNode *readlist(){//建立链表
    struct ListNode *p1,*p2,*head;
    p1=p2=(struct ListNode*)(malloc(sizeof(struct ListNode)));
    scanf("%d",&p1->data);
    head=p1;
    while(p1->data!=-1){
    p2->next=p1;
        p2=p1;
        p1=(struct ListNode*)(malloc(sizeof(struct ListNode)));
        scanf("%d",&p1->data);
    }
    free(p1);
    p2->next=NULL;//一定要最后弄成NULL，没有指向的指针很危险。
    return head;
}
struct ListNode *deletem( struct ListNode *L, int m ){
    while(L->data==m&&L->next!=NULL){//先是找到第一个不为m值的链表
        L=L->next;
    }
    if(L->data==m)return NULL;//经过循环后，已经到达了最后一个链表。
    else {
    int i;
    struct ListNode *q,*w;
    w=q=L;
 	do{//实际上while语句也可以。
 		q=q->next;//让q去探索下一个链表，w来保留上一个链表的位置
 		if(q!=NULL){//一定要判断，如果出现思路里面的错误就会什么也不输出来。
 		if(q->data!=m){
 			w->next=q;//上一个的尾部到新的符合条件的头部
 			w=q;//并把符合条件的头部给w，让w跟踪q，实现链表的连续链接
		 }
		 else if(q->data==m&&q!=NULL){
		 	w->next=NULL;
		 }
	}
	 }while(q!=NULL);
	 return L;
}
}