203. 移除链表元素

题目：

203. 移除链表元素

要求：

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

解答：

独自写出来了，但是代码=写的不好，我的思路是分两步，第一步先把头节点等于目标值的节点全部删除，第二步在遍历后续节点，删除等于目标值的节点，这一步需要一个头节点引用。代码如下：

/**
 * 移除元素，注意头节点的移除
 *
 * @param head 头节点
 * @param val  目标值
 * @return 移除元素后的头节点
 */
public static ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return head;
    }
    // 考虑头部是目标元素，先去除头部是目标元素
    while (head != null && head.val == val) {
        head = head.next;
    }
    ListNode result = head;
    while (result != null) {
        while (result.next != null && result.next.val == val) {
            result.next = result.next.next;
        }
        result = result.next;
    }
    return head;
}

看了下官方题解，官方给出了两个题解，可以理解为一个倒叙删除，一个正序删除。先说倒叙删除，倒叙删除是一个递归的思路，链表天然有递归的特性，这道题目里面就是递归的思路，先判断下一个节点，这样层层递归就是从尾部开始进行判断和删除，要注意递归最重要的就是终止条件，代码如下：

/**
 * 递归的思路
 * @param head
 * @param val
 * @return
 */
public static ListNode removeElements3(ListNode head, int val) {
    if (head == null) {
        return head;
    }
    // 相当于遍历了一遍链表
    head.next =  removeElements3(head.next, val);
    return head.val == val ? head.next : head;
}

官方的第二个题解和我之前的思路是相同的，是我思考的方式问题，这个题解让我学到了在链表的题目中，有一个很重要的思路就是构造虚拟头节点，这样省去了判断头节点的过程，只需要后面一部分，就是判断下一个节点是否等于目标值，如果相等，则让当前节点的指针指向下下个节点，如此遍历到最后一个节点就会删除全部的目标值节点了。代码如下：

/**
 * 构造虚拟节点
 * @param head
 * @param val
 * @return
 */
public static ListNode removeElements2(ListNode head, int val) {
    // 构造虚拟节点
    ListNode virtual = new ListNode(0);
    virtual.next = head;
    ListNode temp = virtual;
    while (temp.next != null) {
        if (temp.next.val == val) {
            temp.next = temp.next.next;
        } else {
            temp = temp.next;
        }
    }
    return virtual.next;
}