代码

法一采用替换删除

但是该方案对于尾节点没用,删除其他节点是没有问题的.

head->A->B->C->D

假如要删除B节点:

1. 让B.val=C.val;
2. B.next=C.next; 上述两步骤就是将C节点的值幅值给了B.其实就相当于是删除了B节点,注意此时的B节点存的值已经不是B了,而是C.

删除链表节点时:

1. 该链是个空链表(那还删个der,直接return)
2. 非空链表删除:

• .删除非尾节点:替换法
• .删除尾节点:保留前驱删除法

    /**
     * 采用替换的思想:不适用于尾节点.因此位于尾节点的删除需要特殊处理(也就是用正常的方式删除为节点,找到尾节点的前驱节点然后直接让尾节点的前驱节点的next为null)
     *
     * @param head
     * @param val
     * @return
     */
    public static ListNode deleteNodeMethod2(ListNode head,int val){

        //空链表
        if (head==null) return head;

        ListNode p = head;
      
        while(p!=null){
            //考虑非尾节点--采用替换的思想
            if(p.val==val&&p.next!=null){//当删除的节点不是尾节点时成立
                p.val=p.next.val;
                p.next=p.next.next;
                return head;
            }
            //考虑尾节点
            if(p.next.val==val&&p.next.next==null){
                p.next=null;
                return head;
            }
            p=p.next;
        }
        return head;
    }

法二 保留前驱删除

单链表删除的常规操作,遍历删除.可以直接定义一个prenext保留当前节点前驱,或者直接用p.next.next遍历比较节点值.

为了保留前驱节点,所以在比较节点值的时候,我们总是站在'待比较节点'一个节点的上一个位置去判断.

考虑几种情况:

1. 空链表情况
2. 非空链表:

• a.删除首节点
• b.删除非首节点

/**
     * 但链表的删除过程当中需要记录前置链表的引用,不然就会断链
     * 这个算是常规解法了
     * @param head ListNode类
     * @param val  int整型
     * @return ListNode类
     */
    public static ListNode deleteNode(ListNode head, int val) {
        // write code here

        //考虑空链表情况
        if(head==null) return head;

        //考虑删除首节点情况
        if(head.val == val){
            head=head.next;
            return head;
        }

        //考虑删除非首节点情况
        ListNode p = head;
        while(p.next!=null){
            if(p.next.val==val) {
                p.next = p.next.next;
                return head;
            }
            p=p.next;
        }
        return head;
    }