[数据结构与算法]链表-巧用哨兵节点

????????哨兵（sentinel）是一个哑对象，可以简化边界条件。是一个附加的链表节点，该节点作为第一个节点，但是它其实并不存储任何东西，只是为了操作的方便而引入的。因此，如果一个链表有哨兵节点的话，那么线性表的第一个元素应该是链表的第二个节点（个位置的时候，需要考虑该位置上原来的节点并没有前驱节点；而如果有哨兵节点的话， 线性表的每个位置的节点都有前驱节点，因此可以统一处理。（注意：哨兵节点根本不出现在线性表中，所以虽然它没有前驱，但是前面的那句话并不矛盾）。

????????哨兵节点广泛应用于树和链表中，如伪头、伪尾、标记等，它们是纯功能的，通常不保存任何数据，其主要目的是使链表标准化，如使链表永不为空、永不无头、简化插入和删除。

问题：删除链表中等于给定值val的所有节点。
1，如果节点在中间，只需将该节点进行删除即可。
2，如果节点在头部，则问题将有点复杂，不能直接将头节点删掉，这样会造成链表的丢失。通过设置哨兵节点，用来临时保存头部节点，最后在计算完毕以后，返回该节点。
代码如下：

struct ListNode* removeElements(struct ListNode* head, int val){

    if (head == NULL)
        return NULL;
    struct ListNode *ret = (struct ListNode*)malloc(sizeof(struct ListNode));
    ret->next = head;
    struct ListNode *pre = ret;
    struct ListNode *cur = head;
    while (cur != NULL)
    {
        if (cur->val == val)
        {
            pre->next = cur->next;
            cur = cur->next;
        }
        else
        {
            cur = cur->next;
            pre = pre->next;
        }
    }
    return ret->next;
}