剑指offer面试题系列

题目：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该结点。

分析

因为给定了此节点指针，指针指向待删除节点。常规方法是：从链表头节点开始遍历，直到节点a的下一个节点指向它。但是这种方法的时间复杂度为O(n),不满足题目要求。

所以只能再想别的办法了。

参考了剑指offer上的思路：只要把要删除结点的下一个结点的指针和下一个结点的数据拷贝到本节点即可。而待删除节点的下一个结点将被直接跳过。

示意图如下图所示：

default

上图的第一种方法就是O(n)复杂度的方法，第二种方法就是O(1)复杂度的方法。

但是如果要删除的是尾节点的话，因为尾节点的下一个结点是null，所以只能按照最常规的办法来。

代码

public static void deleteNode(ListNode head, ListNode DelNode) {
        if (head == null || head.next == null || DelNode == null)
            return;

        if(head.next.next == null) { //链表中只有一个结点
            head.next = null;
            return;
        }

        if(DelNode.next != null) { //链表中有多个结点，要删除的不是尾节点
            DelNode.data = DelNode.next.data;
            DelNode.next = DelNode.next.next;
        }

        else {                    //链表中有多个结点但是要删除的是尾节点
            ListNode p = head.next;
            while(p.next.next != null)
                p = p.next;
            p.next = p.next.next;
        }
    }

备注

需要考虑链表只有一个结点的情况，也需要考虑到要删除的结点是尾节点的方法。另外，如果面试官有要求的话，还需要考虑结点不在链表中的情况。