面试题18_1：删除链表的节点

给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间内删除该结点。假设要删除的结点确实在链表中

思路1：遍历链表，找到下一个节点是需要删除的节点的节点，然后将它的指针指向删除节点的后一个节点，置删除节点为空。设置一个标志位检查是否删除成功，没有删除成功则可能是没有找到该节点。

public class DeleteNode {
    private class Node{
        int val;
        Node next;
        public Node(int val){
            this.val = val;
        }
    }

    /**
     * 常规思路，移动指针
     * @param first
     * @param toBeDel
     */
    public void deleteNode_2(Node first, Node toBeDel) {
        if (first == null || toBeDel == null){
            return;
        }
        //删除的正好是头结点
        if (first == toBeDel){
            first = first.next;
            return;
        }
        //flag记录删除是否成功，也就是检查是否存在删除值
        boolean falg = false;
        Node p = first;
        while (p != null){
            if (p.next == toBeDel){
                p.next = toBeDel.next;
                toBeDel = null;
                falg = true;
            }
            p = p.next;
        }
        if (falg){
           throw new RuntimeException("删除值不存在！");
        }

    }

思路二：不需要查找在链表中的位置，直接找到删除节点的下一个节点，利用下一个节点覆盖上一个节点的方法删除节点，时间复杂度为o（1），由于如果下一个节点为空，则需要重新遍历到最后一个节点，复杂度为o（n），总的时间复杂度为（n-1*O(1)+O(n)）/n。仍未O(1)。依然需要考虑删除节点是否存在。

/**
     * O(1)的时间复杂度，利用被删除节点可以直接找到下一个节点的特性
     * 用下一个节点覆盖被删除节点
     * @param first
     * @param toBeDel
     */
    public static void deleteNode_1(Node first, Node toBeDel) {
        if (first == null || toBeDel == null){
            return;
        }
        if (first == toBeDel){
            first = first.next;
            return;
        }

        //可以直接找到被删除节点的下一个节点
        //考虑被删除节点没有下一个节点的特殊情况
        if (toBeDel.next != null){
            //必须新建一个节点来承接，因为涉及到自己的指针
            Node p = toBeDel.next;
            toBeDel.val = p.val;
            toBeDel.next = p.next;
        }else {
           Node cur = first;
            while (cur.next != toBeDel){
                cur = cur.next;
            }
            cur.next = null;
            toBeDel = null;
        }

    }