题目：
给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点 。
示例1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例2：
输入：head = [], val = 1 输出：[]
示例3：
输入：head = [7,7,7,7], val = 7 输出：[]
这种题型其实就是间接考察大家对于单链表的增删改查的操作，如果对于链表足够熟悉，这种题目做起来就不难理解，做起来就可以得心应手啦~
下面给出两种解题思路：
1.直接使用原来的链表来进行删除操作。（直接删除）
2.设置一个虚拟头结点再进行删除操作。（创建虚拟头节点）
思想1：直接删除
解释：直接删除就是在原来头节点的位置之上，直接进行删除等于val的节点，我们可以给予两个指针，cur指针用来删除等于val的节点，prev指针用来使删除cur的上一节点指向cur的下一节点，然后free掉cur，但是还有一种例外，如果第一个是等于val，我们想要删除的元素呢？所以我们在遍历整个链表之中，需要对以上两种情况进行考虑。
代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur = head,* prev = NULL; while(cur != NULL) { //删除 if(cur->val == val) { if(prev == NULL) { //1.头节点的值等于val cur = head->next; free(head); //删除头节点 head = cur; }else { //2.删除等于val的节点 prev->next = cur->next; free(cur); cur = prev->next; } }else { //往后继续寻找 prev = cur; cur = cur->next; } } return head; }
思想2：创建虚拟头节点
解释：我们可以创建一个新（虚拟）的头节点，利用我们学过的单链表尾插的形式，将原头节点head开始不等于val的节点进行尾插（分为空链表和非空链表两种情况），不等于val的节点在往后寻找前进行free掉即可。我们利用cur指针遍历原链表，用tail指针记录每次尾插后的位置，以免下次尾插需要回头再来寻找，降低了时间复杂度。最重要的一点是，在cur往后挪动之后，我们还需要将虚拟头节点的tail->next置为空，否则会出现野指针的情况。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur = head; struct ListNode* newhead = NULL,* tail = NULL; while(cur != NULL) { if(cur->val != val) { //头插(空链表和非空链表) if(tail == NULL) { newhead = tail = cur; } else { tail->next = cur; tail = tail->next; } //cur往后走，tail的next一定得置空，因为尾节点必须置空 //(可以将code1在循环结束code2的位置置空)。 cur = cur->next; tail->next = NULL; //code1 } else { //删除掉等于val的节点，往后寻找 struct ListNode* del = cur; cur = cur->next; free(del); } } /* // code2 if(tail) tail->next = NULL; */ return newhead; }
