从单向链表中删除指定值的节点
输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。
链表的值不能重复。
构造过程，例如输入一行数据为:
6 2 1 2 3 2 5 1 4 5 7 2 2
则第一个参数6表示输入总共6个节点，第二个参数2表示头节点值为2，剩下的2个一组表示第2个节点值后面插入第1个节点值，为以下表示:
1 2 表示为
2->1
链表为2->1
3 2表示为
2->3
链表为2->3->1
5 1表示为
1->5
链表为2->3->1->5
4 5表示为
5->4
链表为2->3->1->5->4
7 2表示为
2->7
链表为2->7->3->1->5->4
最后的链表的顺序为 2 7 3 1 5 4
最后一个参数为2，表示要删掉节点为2的值
删除 结点 2
则结果为 7 3 1 5 4
数据范围：链表长度满足 1≤�≤1000 1≤n≤1000 ，节点中的值满足 0≤���≤10000 0≤val≤10000
测试用例保证输入合法
输入描述：
输入一行，有以下4个部分：
1 输入链表结点个数
2 输入头结点的值
3 按照格式插入各个结点
4 输入要删除的结点的值
输出描述：
输出一行
输出删除结点后的序列，每个数后都要加空格
思路
如果这题是在LeetCode用核心代码模式做的话，是一道很常规的题目，只需要遍历单向链表，找到与目标值匹配的节点后删除即可
在ACM模式下，输入输出就成了大问题
为了理顺逻辑，最好将删除功能单独写成一个函数
那么，整体逻辑就是：从输入数据中拿到头节点，遍历输入数据，将链表构建好，然后调用删除函数将指定节点删除，最后再把链表的值打印出来
#include<iostream>
using namespace std;
struct ListNode{
};
ListNode* deleteNode(ListNode* head, int val) {//删除链表中值为val的节点
}
int main(){
}
定义结构体
先定义一个结构体作为链表节点(详见：构造链表)
struct ListNode{
int val;
ListNode* next;
ListNode(int x):val(x), next(nullptr){}
};
删除函数
使用dummy进行删除（注意，这里和设计链表中的删除函数还不太一样，这里需要根据节点值进行删除而不是索引值）
ListNode* deleteNode(ListNode* head, int val) {//删除链表中值为val的节点
if(head == nullptr) return nullptr;//特判：如果头结点为空，返回空指针
if(head->val == val) return head->next;//特判：如果头结点的值等于val，直接返回头结点的下一个节点
ListNode* dummy = new ListNode(0);//创建dummy节点,接在头节点之前
dummy->next = head;
ListNode* cur = dummy;
while(cur->next != nullptr){
if(cur->next->val == val){//处理被删除的节点
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}else{
cur = cur->next;
}
}
return dummy->next;
}
主函数
在主函数里，我们需要接受一行输入数据，例如：
6 2 1 2 3 2 5 1 4 5 7 2 2
则第一个参数6表示输入总共6个节点，第二个参数2表示头节点值为2，剩下的2个一组表示第2个节点值后面插入第1个节点值
根据题目描述，我们需要两个两个的从输入数据中取值，过程如下：
取1、2，表示2要接在1后面【链表为2->1】
接下来取2、3，表示3要接在2后面【链表为2->3->1】
然后取5、1，表示5要接在1后面【链表为2->3->1->5】
取4、5，表示5要接在4后面【链表为2->3->1->5->4】...
实际上题目除了要我们从单向链表中删除指定值的节点，还需要我们根据输入数据按照规则来先构建链表
int main(){
//定义几个变量分别接收：链表节点数量（例子中的6）、头节点的值（例子中的2）、待删除节点的值
int n, head_val, val;
cin >> n >> head_val;
ListNode* head = new ListNode(head_val); //创建头结点
for(int i = 0; i < n-1; i++){ //循环插入剩余的n-1个节点
int pre_val, cur_val;//取两个值（如例子中的1、2）
cin >> cur_val >> pre_val; //输入当前节点的值和需要插入的位置的节点的值
ListNode* pre = head;
while(pre != NULL && pre->val != pre_val) //遍历链表，找到需要插入的节点
pre = pre->next;
ListNode* cur = new ListNode(cur_val); //创建当前节点
cur->next = pre->next; //将当前节点插入至链表中
pre->next = cur;
}
}
然后再从输入中获取待删除值，调用删除函数，之后遍历打印链表即可
cin >> val; //输入需要删除的节点的值
head = deleteNode(head, val); //删除节点
while(head != NULL){ //遍历打印链表
cout << head->val << " ";
head = head->next;
}
代码
#include<iostream>
using namespace std;
struct ListNode{
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* deleteNode(ListNode* head, int val) {//删除链表中值为val的节点
if(head == nullptr) return nullptr;//特判：如果头结点为空，返回空指针
if(head->val == val) return head->next;//特判：如果头结点的值等于val，直接返回头结点的下一个节点
ListNode* dummy = new ListNode(0);//创建dummy节点,接在头节点之前
dummy->next = head;
ListNode* cur = dummy;
while(cur->next != nullptr){
if(cur->next->val == val){//处理被删除的节点
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}else{
cur = cur->next;
}
}
return dummy->next;
}
int main(){
int n, head_val, val;
cin >> n >> head_val;
ListNode* head = new ListNode(head_val); //创建头结点
for(int i = 0; i < n-1; i++){ //循环插入剩余的n-1个节点
int cur_val, pre_val;//取两个值（如例子中的1、2）
cin >> cur_val >> pre_val; //输入当前节点的值和需要插入的位置的节点的值
ListNode* pre = head;
while(pre != NULL && pre->val != pre_val) //遍历链表，找到需要插入的节点
pre = pre->next;
ListNode* cur = new ListNode(cur_val); //创建当前节点
cur->next = pre->next; //将当前节点插入至链表中
pre->next = cur;
}
cin >> val; //输入需要删除的节点的值
head = deleteNode(head, val); //删除节点
while(head != NULL){ //遍历打印链表
cout << head->val << " ";
head = head->next;
}
return 0;
}
输入输出总结
其实也没啥好总结的这题，本来以为可以用来当做ACM下链表输入的参考的，结果使用的还是cin
但是观察这题可以发现：ACM下，题目要求的输入有可能不是一次性输入完成的
例如本题，题目举的例子是6 2 1 2 3 2 5 1 4 5 7 2 2，如果一开始没明白题意的话很容易以为输入数据的形式就是这个，导致后续处理很困难
还有就是复习了一下删除指定节点值的操作，练习了链表的构造