原标题 203.移除链表元素 两种思路：直接删除法头体分开处理；虚拟头结点

我的解题思路

思考再三，感觉如果不加虚拟头节点的话，那么头结点要跟其他节点分开处理。于是有2中解决思路。
1、直接删除法头结点与其他节点分开处理：
如果头结点满足条件，那么指针后移，替换为新的头结点；
如果头结点不满足，那么判断其后一个节点是否满足；后一个如果满足，跳过这个指向再后一个；后一个不满足，指针后移；
2、增加虚拟头结点：
增加虚拟头结点之后，原头结点与后续节点统一变为后续节点，统一处理即可。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class _004_203_移除链表元素 {

    public ListNode removeElements(ListNode head, int val) {
//        return removeElements_直接删除头结点与中间节点分开处理(head, val);
        return removeElements_设置虚拟头结点删除(head, val);
    }


    /** 直接删除头结点与中间节点分开处理 */
    private ListNode removeElements_直接删除头结点与中间节点分开处理(ListNode head, int val) {
        ListNode newhead = head;

        // 需要删除头结点的情况
        while (newhead != null && newhead.val == val) {
            newhead = newhead.next;
        }
        // 这里先处理下新的头结点是否为空，否则在后面每个while条件中都要做判断，耗费一定性能
        if (newhead == null) { return null; }

        // 需要删除中间节点的情况
        ListNode node = newhead;
        while (node.next != null) {
            if (node.next.val == val) { //删除
                node.next = node.next.next;
            } else {
                node = node.next; //指针后移
            }
        }

        return newhead;
    }

    /** 设置虚拟头结点删除 */
    private ListNode removeElements_设置虚拟头结点删除(ListNode head, int val) {
        // 虚拟头结点
        ListNode visualHead = new ListNode(0);
        visualHead.next = head;

        ListNode node = visualHead;


        while (node.next != null) {
            if (node.next.val == val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }

        return visualHead.next;
    }


    /** 测试用例 */
    public void test() {
        /*
        输入: 1->2->6->3->4->5->6, val = 6
        输出: 1->2->3->4->5
         */

        int arr1[] = {1, 2, 6, 3, 4, 5, 6};
        test(arr1, 6);

        int arr2[] = {1};
        test(arr2, 1);

        int arr3[] = {1};
        test(arr3, 6);

        int arr4[] = {6, 6};
        test(arr4, 6);
    }

    public void test(int arr[], int value) {
        ListNode head = new ListNode(arr);
        System.out.println("组合完成：");
        System.out.println(head.toLinkedString() + "value: " + value);

        ListNode newHead = removeElements(head, value);
        System.out.println("删除完成:");
        System.out.println(newHead != null ? newHead.toLinkedString() : "newHead为【null】空！");
        System.out.println("-------\n");


//------------------------
//        if (arr.length <= 0) { return; }
//
//        ListNode head = new ListNode(arr[0]);
//        ListNode node = head;
//        for (int i = 1; i < arr.length; i++) {
//            node.next = new ListNode(arr[i]);
//            node = node.next;
//        }
//        System.out.println("组合完成：");
//        System.out.println(head.toLinkedString() + "value: " + value);
//
//        ListNode newHead = removeElements(head, value);
//        System.out.println("删除完成:");
//        System.out.println(newHead != null ? newHead.toLinkedString() : "newHead为【null】空！");
//        System.out.println("-------\n");
    }

    public static void main(String args[]) {
        new _004_203_移除链表元素().test();
    }

}


/*
203. 移除链表元素
https://leetcode-cn.com/problems/remove-linked-list-elements/

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
 */