LeetCode203 移除链表元素

链表

双指针遍历整个链表， pre指针保存当前遍历节点的前一个节点方便删除，cur当前遍历的节点
因为可能删除头节点可以采用哨兵机制

package CLinkedList;

/**
 * @Author Zhou  jian
 * @Date 2020 ${month}  2020/4/9 0009  15:30
 */
public class Problem203 {


    /**
     * 引入一种思想叫哨兵节点
     *
     * @param head
     * @param val
     * @return
     * 如果删除的节点是中间的节点，则问题似乎非常简单：

            选择要删除节点的前一个结点 prev。
            将 prev 的 next 设置为要删除结点的 next

            当要删除的一个或多个节点位于链表的头部时，事情会变得复杂。

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





     */
    public ListNode removeElements(ListNode head, int val) {

        if(head==null) return null;
        //这个很管件哨兵节点
        ListNode virture = new ListNode(-1);
        virture.next = head;

        //保存前一个节点，方便删除
        ListNode prev = virture;
        ListNode temp = head;

        while(temp!=null){
            //发现相等值则直接删除
            if(temp.val==val){
                prev.next = temp.next;
                //在这一步prev还是不能移动思考下为什么
                temp=temp.next;
            } else{
                //不是相等的元素怒则移动指针
                prev = prev.next;
                temp=temp.next;
            }


        }
        //哨兵的下一个节点
        return virture.next;

    }
}