package com.lt.datastructure.LinkedList;

/**

 * leetCode 203题

 * /**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 * 第一种：不使用虚拟头结点

 * 首先考虑头结点，头结点为空，返回null，如果头结点不为空，其值为val，删除头结点。

 * 然后考虑非头结点，遍历链表，如果找到，删除

 */

class Solution {

    public ListNode removeElements(ListNode head, int val) {

        //如果头结点不为空，其值为val，删除头结点

        while(head != null && head.val == val){

            ListNode delNode = head;

            head = head.next;

            delNode.next = null;

        }

        if(head==null) return null;

        //考虑非头结点，遍历链表，如果找到，删除

        ListNode prev = head;

        while(prev.next!=null){

            if(prev.next.val==val){

                ListNode delNode = prev.next;

                prev.next = delNode.next;

                delNode.next = null;

            }else{

                prev = prev.next;

            }

        }

        return head;

    }

    /**

     * 第二种：使用虚拟头结点

     */

    class Solution2 {

        public ListNode removeElements(ListNode head, int val) {

            //使用虚拟头结点简化第一种方式的代码

            ListNode dummyhead = new ListNode(-1);

            //指向head头结点

            dummyhead.next = head;

            ListNode prev = dummyhead;

            while(prev.next!=null){

                if(prev.next.val == val){

                     prev.next = prev.next.next;

                }else{

                    prev = prev.next;

                }

            }

            return dummyhead.next;

        }

    }

}