【力扣-数据结构和算法-头哨兵】移除链表元素

题目：

给你一个链表的头节点 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
输出：[]

题解：

本题我们采用头哨兵法来解，首先，什么是头哨兵？

简单来说，头哨兵就是本来已经给你一个链表，你自己新建一个相同的结构体guide，将其next指向你的已知的第一个链表节点，这就叫头哨兵。那么用头哨兵有什么好处呢？

当我们有头哨兵的时候，我们知道，头哨兵的下一个节点就是我们的首节点，那么如果我们链表为空的话，正常情况下我们要判空，但是如果有头哨兵就不一样了，就不可能为空，这样就简便了很多，减少了错误的出现几率；

下面我们用头哨兵的方式来解决上面的例题：

struct ListNode* removeElements(struct ListNode* head, int val)
{
    //创建头哨兵
    struct ListNode* phead=(struct ListNode*)malloc(sizeof(struct ListNode));
    phead->next=head;
    //记录头哨兵的下一个节点，其并非是head，因为head也可能被删除
    struct ListNode* temp = phead;
    while(phead->next!=NULL)//头哨兵的下一个就是第一个节点
    {
        if(phead->next->val==val)//符合题意，释放该节点
        {
            struct ListNode* tmp = phead->next->next;
            free(phead->next);
            phead->next=tmp;
        }
        else//不符合题意，往后走
        {
                phead=phead->next;
        }
    }
    return temp->next;
}

OK！关注一波，我会回访的哦！