package 链表;
/**
 * https://leetcode-cn.com/problems/remove-linked-list-elements/
 *  思路覆盖法(后一个结点值覆盖掉当前结点，然后再处理一下指针指向，实现删除效果)
 * 
 * @author Huangyujun
 *
 */
public class _203_移除链表元素 {
    //递归
    class Solution {
        public ListNode removeElements(ListNode head, int val) {
            if (head == null) {
                return head;
            }
            head.next = removeElements(head.next, val);
            return head.val == val ? head.next : head;
        }
    }
    //我这道题这样干的话，就得去分开讨论最后一个结点是val时要怎么处理了
//    public ListNode removeElements2(ListNode head, int val) {
//        if(head == null) return null;
//        //好处，我想到了就是定义进入一个虚拟头结点
//        ListNode newHead = new ListNode(0);
//        newHead.next = head;
//        while(head != null) {
//            if(val == head.val) {    //找到了(还得考虑head.next是否为空，同时若当前待删除结点是最后一个的话，咱还得找到前一个，（解决可以定义一个prev 指针变量）)
//                head.val = head.next.val;
//                head.next = head.next.next;
//            }else {
//                head = head.next;
//            }
//            
//        }        
//        return newHead.next;
//    }
    //官网：秒啊： while (temp.next != null) ，
    //如果我直接在 while(head != null) 改成： while(head.next != null) 导致到了最后一个结点的next是空，直接跳出循环，最后一个结点得不到判断
    // 官网的小心机是：加上了：（将自身变成了一个前一个结点位置prev，判断自身的next 是否等于val，若等于，自身就是待删除结点的前一个了，秒啊）
    /** 将开始遍历的位置移动到了虚拟头结点的位置（然后，通过next进行判断），这样就可以拿到最后一个结点了
              dummyHead.next = head;
            ListNode temp = dummyHead;
            while (temp.next != null) {
     */
    class Solution2 {
        public ListNode removeElements(ListNode head, int val) {
            ListNode dummyHead = new ListNode(0);
            dummyHead.next = head;
            ListNode temp = dummyHead;
            while (temp.next != null) {
                if (temp.next.val == val) {
                    temp.next = temp.next.next;
                } else {
                    temp = temp.next;
                }
            }
            return dummyHead.next;
        }
    }
}