面试题13：在O（1）时间删除链表结点

题目：

在给定单向链表的头指针和一个结点指针，定义一个函数在O（1）时间删除该结点。

思考：

链表结构一般需要从头遍历，时间复杂度O（n）。但我们可以假定已经给出需要删除的结点，当删除结点i时，把结点i的下一个结点j覆盖到i，再把j删除。这种方法可以不用再遍历链表。

注意点：删除的结点如果是尾结点，仍需重新遍历链表，时间复杂度为O（n）。
总的平均时间复杂度：[(n-1)*O(1)+O(n)]/n = O (1)

实现：

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();

        Node node1 = new Node();
        Node node2 = new Node();
        Node node3 = new Node();
        Node node4 = new Node();

        node1.value = 1;
        node2.value = 2;
        node3.value = 3;
        node4.value = 4;

        node3.next = node4;
        node2.next = node3;
        node1.next = node2;
        //删除头结点
//        Node node = solution.deleteNode(node1, node1);
//        printLink(node);

        //删除中间结点
//        solution.deleteNode(node1, node3);
//        printLink(node1);
        //删除尾结点
        solution.deleteNode(node1, node4);
        printLink(node1);

    }

    /**
     * 打印
     * @param node1
     */
    private static void printLink(Node node1) {
        while (node1 != null) {
            System.out.print(node1.value + "  ");
            node1 = node1.next;
        }
        System.out.println();
    }

    public void deleteNode(Node head, Node toBeDeleted) {
        //判断
        if (head == null || toBeDeleted == null) {
            return;
        }

        //后一个结点覆盖前一个结点
        if(toBeDeleted.next != null ) {
            toBeDeleted.value = toBeDeleted.next.value;
            toBeDeleted.next = toBeDeleted.next.next;
        } else if (head == toBeDeleted) {
            //只有一个结点的情况，实现不了，java是值传递，并不能将原来的参数改变
            head = toBeDeleted = null ;
        } else {
            //尾结点
            Node preNode = head;
            while (preNode.next != toBeDeleted ){
                preNode = preNode.next;
            }
            preNode.next = null;
        }
    }
}

/**
 * 自定义结点类
 */
class Node{
     Integer value;
     Node next;
}