Question

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

在单向链表中删除一个结点，最常规的做法无疑是从链表的头结点开始，顺序遍历查找要删除的结点，并在链表中删除该结点。

比如在图3.3（a）所示的链表中，我们想删除结点i，可以从链表的头结点a开始顺序遍历，发现结点h的m_pNext指向要删除的结点i，于是我们可以把结点h的m_pNext指向i的下一个结点即结点j。指针调整之后，我们就可以安全地删除结点i并保证链表没有断开（如图3.3（b）所示）。这种思路由于需要顺序查找，时间复杂度自然就是O（n）了。

图3.3　在链表中删除一个结点的两种方法

注：（a）一个链表。（b）删除结点i之前，先从链表的头结点开始遍历到i前面的一个结点h，把h的m_pNext指向i的下一个结点j，再删除结点i。（c）把结点j的内容复制覆盖结点i，接下来再把结点i的m_pNext指向j的下一个结点之后删除结点j。这种方法不用遍历链表上结点i前面的结点。

之所以需要从头开始查找，是因为我们需要得到将被删除的结点的前面一个结点。在单向链表中，结点中没有指向前一个结点的指针，所以只好从链表的头结点开始顺序查找。

那是不是一定需要得到被删除的结点的前一个结点呢？答案是否定的。我们可以很方便地得到要删除的结点的一下结点。如果我们把下一个结点的内容复制到需要删除的结点上覆盖原有的内容，再把下一个结点删除，那是不是就相当于把当前需要删除的结点删除了？

我们还是以前面的例子来分析这种思路。我们要删除结点i，先把i的下一个结点j的内容复制到i，然后把i的指针指向结点j的下一个结点。此时再删除结点j，其效果刚好是把结点i给删除了（如图3.3（c）所示）。

上述思路还有一个问题：如果要删除的结点位于链表的尾部，那么它就没有下一个结点，怎么办？我们仍然从链表的头结点开始，顺序遍历得到该结点的前序结点，并完成删除操作。

最后需要注意的是，如果链表中只有一个结点，而我们又要删除链表的头结点（也是尾结点），此时我们在删除结点之后，还需要把链表的头结点设置为NULL。

有了这些思路，我们就可以动手写代码了。下面是这种思路的参考代码：

接下来我们分析这种思路的时间复杂度。对于n－1个非尾结点而言，我们可以在O（1）时把下一个结点的内存复制覆盖要删除的结点，并删除下一个结点；对于尾结点而言，由于仍然需要顺序查找，时间复杂度是O（n）。因此总的平均时间复杂度是[（n－1）^*O（1）＋O（n）]/n，结果还是O（1），符合面试官的要求。

值得注意的是，上述代码仍然不是完美的代码，因为它基于一个假设：要删除的结点的确在链表中。我们需要O（n）的时间才能判断链表中是否包含某一结点。受到O（1）时间的限制，我们不得不把确保结点在链表中的责任推给了函数DeleteNode的调用者。在面试的时候，我们可以和面试官讨论这个假设，这样面试官就会觉得我们考虑问题非常全面。

源代码：

本题完整的源代码详见13_DeleteNodeInList项目。

测试用例：

- 功能测试（从有多个结点的链表的中间删除一个结点，从有多个结点的链表中删除头结点，从有多个结点的链表中删除尾结点，从只有一个结点的链表中删除唯一的结点）。

- 特殊输入测试（指向链表头结点指针的为NULL指针，指向要删除的结点为NULL指针）。

本题考点：

- 考查应聘者对链表的编程能力。

- 考查应聘者的创新思维能力。这道题要求应聘者打破常规的思维模式。当我们想删除一个结点时，并不一定要删除这个结点本身。可以先把下一个结点的内容复制出来覆盖被删除结点的内容，然后把下一个结点删除。这种思路不是很容易想到的。

- 考查应聘者思维的全面性。即使应聘者想到删除下一个结点这个办法，也未必能通过这轮面试。应聘者要全面考虑到删除的结点位于链表的尾部及输入的链表只有一个结点这些特殊情况。