问题描述：给定单向链表的头指针和一个节点指针，定义一个函数在o（1）时间内删除该节点。
问题分析：在单链表中删除一个节点，最常规的办法是从链表的头结点开始遍历，找到需要删除的结点就删除。但是平均时间复杂度是o（n）。
推荐算法：
根据需要删除的节点指针p，可以找到p的下一个节点q，将q的值赋值给p后再将p的指针指向q，即用q覆盖p，则达到删除的目的。
如果链表中只有一个节点，在删除该节点后需要把链表的头结点置为null。如果需要删除的是尾节点，即p的下一个节点q为null，则还是需要顺序遍历链表，找到p的前序节点进行删除操作。对于n-1个非尾节点，O(1)时间内可以删除，如果是尾节点则为O(n)，平均时间复杂度为[O(1)∗(n−1)+O(n)∗1]/n，时间复杂度还是O(1)O。符合要求。不过该方法并没有判断需要删除的节点是否在链表中，为达到时间复杂度为O(1)的要求，将判断节点是否存在的责任推给了该方法的调用者。
/ ** * 平均时间复杂度为O(1)，删除链表节点 * @param head 头结点 * @param nodeToBeDeleted 待删除节点 */ public void deleteNode(ListNode head, ListNode nodeToBeDeleted) { if(head == null || nodeToBeDeleted == null) return; // 要删除的节点不是尾节点 O(1) if (nodeToBeDeleted.next != null) { nodeToBeDeleted.val = nodeToBeDeleted.next.val; nodeToBeDeleted.next = nodeToBeDeleted.next.next; } else if(head == nodeToBeDeleted) { // 要删除头节点，而且链表只有一个节点 O(1) nodeToBeDeleted = null; head = null; } else { ListNode tmp = head; // 要删除尾节点，而且链表有多个节点 O(n) while (tmp.next != nodeToBeDeleted) { tmp = tmp.next; } tmp.next = null; nodeToBeDeleted = null; } } 参考资料 来源于 剑指offer 何海涛 电子工业出版社