补充：OJ题4: 移除链表元素

嗨!小伙伴们,大家还记得这道题吗?

刚才我们讲解了方法一,接下来我们来讲讲方法二。

法二： 我们可以用一个pcur变量依次遍历原链表的每一个结点,如果pcur->val等于要删除的数据val,那么执行链表的删除操作。

首先，我们定义一个哨兵结点（只是指向头结点，里面没有任何数据，便于执行删除操作），将哨兵结点的next指针指向头结点； 定义一个pcur变量,依次遍历链表的每一个结点。定义一个prev指针,用来保存被删除结点的前一个结点。

当pcur指向第一个结点时,进入循环,开始判断链表中每一个结点的数据域是否为val,如果等于val,那么执行删除操作; 如果不等于val,prev指针保存pcur的位置,pcur指向下一个结点,继续往后判断。

第一次：(我们假设val的值为6)pcur指向的结点的数据域不是val(pcur->val != val), 那么就把pcur的值赋给prev,pcur指向下一个结点。

第二次：pcur指向的结点的数据域不是val(pcur->val != val), 那么就把pcur的值赋给prev,pcur指向下一个结点。

第三次：pcur指向的结点的数据域为val(pcur->val == val), 那么就把pcur用一个临时变量del保存起来,prev指向pcur的下一个结点,同时释放del,此时pcur为一个野指针,那么就把pcur指向prev结点的next指针。

prev->next = pcur->next;        //prev指针指向pcur的下一个结点
struct ListNode* del = pcur;    //用临时变量del来保存pcur结点
free(del);                      //将del结点释放,pcur现在是野指针
pcur = prev->next;              //pcur指向prev结点的next指针

亦或者,我们也可以这样写:

prev->next = pcur->next;          //prev结点的next指针指向pcur的下一个结点
struct ListNode* del = pcur;      //用临时变量del保存pcur结点
pcur = pcur->next;                //pcur结点指向下一个结点
free(del);                        //释放del结点,对pcur没有造成影响

第四次: pcur指向的结点的数据域不是val(pcur->val != val), 那么就把pcur的值赋给prev,pcur指向下一个结点。

第五次: pcur指向的结点的数据域不是val(pcur->val != val), 那么就把pcur的值赋给prev,pcur指向下一个结点。

第六次:  pcur指向的结点的数据域不是val(pcur->val != val), 那么就把pcur的值赋给prev,pcur指向下一个结点。

第七次: pcur指向的结点是val,执行删除操作。

最后我们找到第一个结点,释放哨兵结点,本题完成。

本题代码如下：

 
 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    //定义一个哨兵结点,便于后续执行删除操作
    ListNode* node =(ListNode*) malloc(sizeof(ListNode));
    //哨兵结点的next指向头结点
    node->next = head;
 
    //prev指向哨兵结点
    ListNode* prev = node;
    //pcur指向头结点,依次遍历链表中每一个结点
    ListNode* pcur = head;
 
    while(pcur!=NULL){
        //从头结点开始,一直到NULL结束
        if(pcur->val == val){
            //结点的值为val,执行删除操作
            prev->next = pcur->next;            //prev指向pcur的下一个结点
            ListNode* del = pcur;               //用临时变量del将pcur保存
            pcur = pcur->next;                  //pcur指向下一个结点
            free(del);                          //释放del结点
        }else{
            //结点的值不是val
            prev = pcur;
            pcur = pcur->next;
        }
    }
    head = node->next;                       //头结点是哨兵结点的下一个结点
    free(node);                              //释放哨兵结点
    return head;                             //返回头结点
 
}