单链表结点删除

单链表结点删除

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

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 结尾无空行 我的思路

先弄两个指针,让其中的p指向链表头,q置为NULL(q指向的是p的上一个节点)。然后弄个循环不断地判断 移动 判断,在程序里面有好几个容易出错的地方,首先一定要判断q是否为空,为什么要判断 p 呢!因为我们要删的数可能在第一个节点,在第一个节点的话我们无法将p赋值给q,如果在这里把p赋给q的话(p将指向下一节点),就会跳过q(赋值后的)指向的节点的判断(判断是否是m),还有一个要注意的是如果q为空,我们一定要移动链表的头结点 L,使 L 指向下一节点。

代码 struct ListNode* readlist() { struct ListNode* head = NULL, * p = NULL, * last=NULL; int number; last = head; do { scanf("%d", &number); //输入值 if (number != -1) //等于 -1 跳出循环 { p = (struct ListNode*)malloc(sizeof(struct ListNode)); //为节点开辟空间 p->data = number; //给节点赋值 p->next = NULL; //将节点指向的位置 设置成NULL if (last==NULL) //判断是否有 头结点 { head = p; } else last->next = p; //连接新节点p last = p; //last指向新的链尾 } else break; } while (number != -1); return head; //返回链表的头节点 } struct ListNode* deletem(struct ListNode* L, int m){ struct ListNode* p = L, * q = NULL; while(p) { //判断是否到达链尾 if (p->data == m) { //若节点的值等于 m if (q) { //判断 q 是否为空 q->next = p->next;//保存 p 指向下一节点的指针 其实就是把 p->next 指向的节点和 q 节点链起来 free(p); //释放内存 p = q->next; //因为释放内存后 p的指向改变了 需要重新设置 不能直接让p指向下一个节点 } else { L = p->next; // q为空 代表链表的第一个节点的值等于m 是要删除的节点 。需要移动链表的头结点,不然的话 L 将指向一个奇怪的地方。 free(p); //释放内存 p = L; //释放内存后 p的指向改变了 让 p 指向新的链表头 } } else { q = p; //移动节点 p = p->next; } } return L; //返回链表的头节点 }

加油啊!

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwjzxw.html