[数据结构与算法]链表——移除链表元素

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

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

输入：head = [], val = 1
输出：[]

输入：head = [7,7,7,7], val = 7
输出：[]

方法：

• 直接使用原来的链表来进行删除操作。
• 设置一个虚拟头结点在进行删除操作。

1，不添加虚拟节点方式：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
    	//删除头节点
        while(head != null && head.val == val){
            head = head.next;
        }
        //为null提前退出
        if(head == null){
            return head;
        }
        ListNode pre_node = head;
        ListNode cur_node = head.next;
        while(cur_node != null){
            if(cur_node.val == val){
            	//删除该节点
                pre_node.next = cur_node.next;
            }else{
                pre_node = cur_node;
            }
            //移到下一节点
            cur_node = cur_node.next;
        }
        return head;
    }
}

2,，添加虚拟节点

class Solution {
    public ListNode removeElements(ListNode head, int val) {
       //为null提前退出
       if(head == null){
           return head;
       }
       //设置虚拟节点作为头节点，移除头节点方式就与其他节点一样了
       ListNode dummy = new ListNode(-1, head);
       ListNode pre_node = dummy;
       ListNode cur_node = head;
       while(cur_node != null){
           if(cur_node.val == val){
           	   //删除该节点
               pre_node.next = cur_node.next;
           }else{
               pre_node = cur_node;
           }
           //移到下一节点
           cur_node = cur_node.next;
        }
        return dummy.next;
    }
}