移除链表元素

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

• 知识点单链表的应用

三种方式

• 1.常规方式用单链表头指针，以及两个结构体指针指针来解决
• 2.创建一个新节点，将val不等于val的节点尾插到新的结点
• 3.利用哨兵简化

第一种

• 思路
• 
  
  

struct ListNode* removeElements(struct ListNode* head, int val){
 struct ListNode* cur=head;
struct ListNode* prev=NULL;
//1.头部data就是val
//2.非头部的data是val
//即while(cur!=null)
while(cur)
{
    if(cur->val==val)
  {
       if(cur==head)
      {
        //更新头指针
         head=head->next;
         free(cur);//free掉原先的头部
         cur=head;//cur在指向head，以便于后续判断
       }
       else
      {
        prev->next=cur->next;
        free(cur);
        cur=prev->next;
       }
    }
     else
     {
       prev=cur;
       cur=cur->next;
      }

}
return head;//返回头指针的地址
}

第二种----把值不是val的拿下来链接到新的节点上去

• 思路
  
  

struct ListNode* removeElements(struct ListNode* head, int val){
 struct ListNode* cur=head;
struct ListNode* newnode=NULL;
struct ListNode* tail=NULL;
while(cur)
{
    if(cur->val!=val)
    {
        if(tail==NULL)
        {
            newnode=tail=cur;//tail为空说明第一次插入
        }
        else
        {
            tail->next=cur;
            tail=tail->next;
   }
   //判断完后，继判断下一个结点
   cur=cur->next;
        
    }
    //如果是val那么释放掉那个结点，将
    else
    {
        struct ListNode* del=cur;//将要释放的结点保存在del,释放掉
        cur=cur->next;//指向下一个结点继续判断val值
        free(del);    
    }
}
//如果tail不为空，那么tail的next为null
if(tail)
{
    tail->next=NULL;
}
return newnode;
}

第三种利用哨兵头(对第二种方法的简化，不用考虑第一次插入的问题，直接尾插到guard的后面）

struct ListNode* removeElements(struct ListNode* head, int val){
 struct ListNode* cur=head;
struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* tail=guard;
while(cur)
{

    if(cur->val!=val)
    {
        
        tail->next=cur;
        tail=tail->next;
        cur=cur->next;

    }
    else
    {
        struct ListNode* del=cur;
        cur=cur->next;
        free(del);
    }
}
if(tail)
{
    tail->next=NULL;
}
head=guard->next;
return head;
}