第一题：删除链表中的指定节点
问题描述：
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
题目接口：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteNode(struct ListNode* head, int val){
}问题解答思路：
这道题的意思就是要删除链表中的值等于val的节点，但是这道题需要考虑两种情况。
第一种情况就是删除头节点，第二种情况就是删除不是头节点的情况。这两种情况可是不一样的，假如我们把这两种情况混为一谈这道题是不一定能通过的。所以我们要分两种情况来解决这道题。
解法1：分头节点与一般节点两种情况
struct ListNode* deleteNode(struct ListNode* head, int val){
while(head!=NULL&&head->val==val){//处理头节点的问题
struct ListNode*temp = head;
head = head->next;//移动head删掉头节点
free(temp);
}
struct ListNode*temp = head;
struct ListNode*cur = head->next;//因为头节点已经处理完了，所以再让cur指向head是没有意义的，所以让cur指向第二个节点
while(cur){
if(cur->val==val){
temp->next = cur->next;//删除值为val的节点
cur = cur->next;//再次移动cur
}
else{
temp = cur;//记录cur的原来位置
cur = cur->next;//cur向下一位移动
}
}
return head;
}解法2：加一个节点在头节点前面
思路：既然第一种解法要我们处理两种情况，那我们可不可以把这两种解法换成一种解法呢？当然可以，只要我们人为的创建一个节点就可以将将头节点的情况去掉了。
虚拟头节点法：
struct ListNode* deleteNode(struct ListNode* head, int val){
struct ListNode* dumy = (struct ListNode*)malloc(sizeof(struct ListNode));//使用malloc搞出来一个虚拟节点。
struct ListNode* cur = head;
struct ListNode* temp = dumy;
dumy->next = head;//将dump连接在head的前面，是dumy成为一个头节点
while(cur){//第一种方法中的普通节点处理法，这次就要从head开始删除了。
if(cur->val==val){
temp->next = cur->next;
cur = cur->next;
temp = cur;
}
else{
temp = cur;
cur = cur->next;
}
}
head = dumy->next;//返回值是dumy->next。这一点要注意
free(dumy);//释放掉dumy,防止内存泄漏
return head;//返回头节点。
}解法三：尾插法
对于愚笨的我来说，这种方法是我最难理解的，那我就在这里重点讲解一下吧。
首先来看一下代码:
尾插法代码：
struct ListNode* deleteNode(struct ListNode* head, int val){
struct ListNode* cur = head;
struct ListNode* tail = NULL;
struct ListNode* newnode = NULL;
while(cur){
if(cur->val!=val){
if(tail == NULL){
tail =newnode = cur;
}
else{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
tail->next = NULL;
}
else{
struct ListNode* del = cur;
cur = cur->next;
free(del);
}
}
return newnode;
}尾插法解法过程演示：
首先我们要明确的是，不论这道题怎么写这道题都有三种情况要处理。即：删除头节点，删除中间节点，删除尾节点。
1.删除头节点：
假如我们的链表是：-3->5->99，要删除的值是-3，也就是要删除头节点
现在我们看看代码是如何走的：下面代码是删除头节点时的执行代码
struct ListNode* cur = head;
struct ListNode* tail = NULL;
struct ListNode* newnode = NULL;
else{
struct ListNode* del = cur;
cur = cur->next;
free(del);
}这段代码执行以后：
tail,newnode,cur三者与链表的关系就变成这样了：
然后我们就不用删除头节点了，剩下的节点的处理方式就是下面代码：
struct ListNode* cur = head;
struct ListNode* tail = NULL;
struct ListNode* newnode = NULL;
while(cur){
if(cur->val!=val){
if(tail == NULL){
tail =newnode = cur;
}
else{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
tail->next = NULL;
}现在，因为tail节点指向空，cur->val!=val。所以执行第二个if语句。
但是此时tail还是要与cur指向的下一个元素有联系。其实这也可以把tail看作是cur的一个拷贝，既然是拷贝tail指向的下一个节点当然就是cur指向的下一个节点了。
代码
cur = cur->next;
tail->next = NULL;再来看看这一段代码的示意图：
在这里可以看到在执行了cur=cur->next的操作以后，将tail的next置空的操作。这是要特别注意的一点。因为这样的操作可以避免野指针的问题。当然还有一点需要注意的就是这两个代码执行顺序的问题。如果先执行tail->next = NULL的操作，再执行cur = cur->next的操作将会导致栈溢出的问题。原因很简单，因为tail与cur一开始指向的是同一块空间，假如先置空tail的next，cur将找不到自己的next。
最后，执行以下代码：
else{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
tail->next = NULL;
最后再返回newnode，就得到我们想要得到的结果了。
return newnode;其它的情况这个代码也是可以过的，在这里就不啰嗦了。
文章来源地址https://www.toymoban.com/news/detail-424358.html
文章来源：https://www.toymoban.com/news/detail-424358.html
到了这里，关于关于链表的题目—leetcode的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
