【力扣】移除链表元素203
1.前言
这里开始介绍从网上一些刷题网站上的题目，在这里做一些分享，和学习记录。 先来介绍一些力扣的OJ题目。 这里的OJ就是我们不需要写主函数，力扣会提供一个接口，在力扣中会调用我们所写的代码和它后台的匹配，从而判断我们写的代码正确性。
在力扣的题目中一般会给一些示例，就像这样：
当我们写完代码时可以点击运行，这时下面会出现一些测试用例，就像下面这样：
但是并不是给了运行成功就一定能成功，必须点击上面的提交，通过了才是真正的正确，就像下面这样：
2. 题目描述
3. 题目分析
这里题目明确指出需要返回的是新的链表，所以要返回一个新链表的头节点。 当我们没有任何思路时，可以先看看它给的示例，先进行一下分析。
要找到不是val值的节点，那么首先肯定要先遍历原来的链表，把不是的插入到新的链表中。
那首先就得先定义一个新的链表的头指针struct ListNode* newhead=NULL;为了方便实现插入，使用尾插，再定义一个新链表的尾指针方便插入struct ListNode* tail=NULL;接下来就需要原链表中找出不是val值的节点，然后尾插就行。
怎么找出不是val值的节点？
为了不使原链表中的头节点丢失，用定义一个cur指针代替，struct ListNode* cur=head;。
用一个while循环，当cur为空时就结束，也就是cur已经把原链表遍历完了。
这里需要先考虑一下如果原链表为空，那就直接返回NULL就行。
在循环中怎么写找到val的代码？
那就先让cur往后走，当走到cur->val=val结束，所以这里插入的条件就是if(cur->val!=val)，然后开始实现尾插。
3.1 不带哨兵位
这里还需要先判断一下新的链表是不是为空，如果为空，那就直接将cur=newhead，并且更新一下tail=cur;如果不为空，那就直接实现尾插。
if(cur->val!=val)
{
if(newhead==NULL)
{
newhead=cur;
tail=cur;
}
else
{
tail->next=cur;
tail=tail->next;
}然后让cur继续往后遍历。 当找到原链表中节点值为val的节点是时，就删除：
struct ListNode* tmp=cur;
cur=cur->next;
free(tmp);这里加一个尾指针的判断
if(tail)
{
tail->next=NULL;
}最后直接返回新节点的头指针。
3.2 带哨兵位
使用带哨兵位的新链表， newhead=tail=(struct ListNode*)malloc(sizeof(struct ListNode));就不需要判断新链表是否为空。
其它地方都与不带哨兵位一样，不过最后得把申请的哨兵位释放掉，返回的是哨兵位的后一个节点。
struct ListNode* tmp=newhead;
newhead=newhead->next;
free(tmp);
return newhead; 
4. 附代码
4.1 不带哨兵位
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newhead=NULL;
struct ListNode* tail=NULL;
struct ListNode* cur=head;
while(cur)
{
if(cur->val!=val)
{
if(newhead==NULL)
{
newhead=cur;
tail=cur;
}
else
{
tail->next=cur;
tail=tail->next;
}
cur=cur->next;
}
else{
struct ListNode* tmp=cur;
cur=cur->next;
free(tmp);
}
}
if(tail)
{
tail->next=NULL;
}
return newhead;
}4.2 带哨兵位
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* newhead=NULL;
struct ListNode* tail=NULL;
struct ListNode* cur=head;
newhead=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
while(cur)
{
if(cur->val!=val)
{
tail->next=cur;
tail=tail->next;
cur=cur->next;
}
else{
struct ListNode* tmp=cur;
cur=cur->next;
free(tmp);
}
}
tail->next=NULL;
struct ListNode* tmp=newhead;
newhead=newhead->next;
free(tmp);
return newhead;
}