删除链表中等于给定值 val 的所有结点（三种方法深入解析）

又见面啦，接下来的链表相关Oj题目我会根据我自己的理解来给大家讲解，包括解析和代码，希望你可以对链表有更加深入的理解！！

题目：

先上链接：

OJ题目

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

方法一：迭代

想法：遍历链表，找到这个val前面一个结点，让这个结点指向val的next

注意：在寻找为给定值的结点时，需要先判断结点是否为空结点

if (head != nullptr && head->val == val) {head = head->next;
}

结果如下：

struct ListNode* removeElements(struct ListNode* head, int val) {if (head != nullptr && head->val == val) {head = head->next;
}if(NULL==head){return head;}struct ListNode*pre=head;while(pre->next!=NULL){if(pre->next->val==val){pre->next=pre->next->next;}else {pre=pre->next;}}return head;}

方法二：双指针

设置两个指针，值为head

cur右移判断他的val 是否为要删除的值，如果不是pre右移

直到cur->val==val;这个时候的pre就是这个需要删除结点的前结点，让pre->next=cur->next，遍历完整个链表就可以了

看一下代码

struct ListNode* removeElements(struct ListNode* head, int val){while (NULL != head && head->val == val) {head = head->next;}struct ListNode* cur = head;struct ListNode* pre = head;while (cur != NULL) {if (cur->val == val) {pre->next = cur->next;} else {pre = cur;}cur = cur->next;}return head;
}

虚拟头结点

可以通过在头结点前增加虚拟头结点，这样子头结点就变成了普通结点

看代码

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode*dummyhead=malloc(sizeof(struct ListNode));if(dummyhead==NULL){return NULL;}dummyhead->next=head;struct ListNode*cur=dummyhead;while(cur->next!=NULL){if(cur->next->val==val){cur->next=cur->next->next;}else{cur=cur->next;}}struct ListNode*retNode=dummyhead->next;free(dummyhead);return retNode;}