力扣203. 移除链表元素

题目描述：

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

 

 

typedef struct ListNode Node;
struct ListNode* removeElements(struct ListNode* head, int val){
    //双指针
    //定义两个指针prev cur
    //最初始的情况的是prev=NULL,cur=head;
    Node*prev=NULL,*cur=head;
    //结束的情况时prev指向最后一个元素，cur指向NULL
    //所以循环控制条件为cur
    while(cur)
    {
        //如果cur->val==val
        //就要删除掉这个元素
        //prev cur
        // 1    6    2   3
        //prev->next=cur->next
        //删除这个元素
        //free(cur);
        //然后再把cur=prev->next;
        if(cur->val==val)
        {
            //如果第一个节点就是val呢？
            //此时prev=NULL;
            //没法按照prev->next=cur->next;free(cur);cur=prev->next;这个逻辑去删除这个节点
            //所以
            //if的条件既可以是cur==head也可以是prev==NULL
            //此时
            //重新定义头节点：head=cur->next
            //然后删除掉这个元素： free(cur);
            //再把head赋给cur:cur=head;
            if(cur==head)//if(prev=NULL)
            {
                head=cur->next;
                free(cur);
                cur=head;
            }
            else
            {
                prev->next=cur->next;
                free(cur);
                cur=prev->next;//必须有这一步
                //如果最后一个数是val，程序要走到prev指向最后一个数时才算结束
                //这个时候，while的循环判断条件里的cur是一个野指针
                //所以要把cur置为NULL,即cur=prev->next
                //删除了val后,prev->next为NULL
            }


        }
        //如果cur->val!=val就要两个指针一起向后走
        //把cur给prev,然后cur往后走
        //prev=cur;
        //cur=cur->next;
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    //题目要求返回新的头节点-return head;
    return head;
}