[数据结构与算法]leecode:203. 移除链表元素

leecode:203. 移除链表元素

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

思路：
有两种方法：不添加虚拟的头结点 和 添加虚拟头结点
1）对于不添加虚拟头结点，考虑三种情况：
a. 链表为null
b.head.val==val
c.正常情况

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 //不添加虚拟头结点
class Solution {
    public ListNode removeElements(ListNode head, int val) {
		//头结点的值也为val
		while(head!=null&&head.val==val){
			head = head.next;
		}
		//链表为空
		if(head==null){
			return null;
		}
		//正常情况，遍历链表
		ListNode pre = head; // 定义pre结点，得到筛选后的链表
		ListNode cur = head.next; //用于遍历链表
		while(cur!=null){
			//pre是根据cur的val来决定如何移动的
			if(cur.val==val){
				pre.next = cur.next; // 删除此时这个结点
			}else{
				pre = cur; //向前移动了pre
			}
			cur = cur.next; //向前推进cur
		}
		return head;
    }
}

2)创建一个虚拟的头结点
此时无需考虑第一个结点的值是否等于val了
仅考虑两种情况：
a.链表是否为null
b.正常遍历删除

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
		//链表为null
		if(head==null){
			return null;
		}
		//正常遍历删除
		//创建新的head结点
		ListNode newHead = new ListNode(-1, head);
		ListNode pre = newHead;
		ListNode cur = newHead.next;
		while(cur!=null){
			if(cur.val==val){
				pre.next = cur.next;
			}else{
				pre = cur;
			}
			cur = cur.next;
		}
		return newHead.next;
    }
}