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

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

 链表结点与函数的定义如下：

struct ListNode
{
    int m_nValue;
    ListNode* m_pNext;
};

void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted);

删除结点的操作我们经常碰到，比如一个链表A->B->C->D->E->F->G。如果我们要删除结点E，那么我们只需要让结点D的指针指向结点F即可，但是我们现在只给出链表头结点的指针以及结点E的指针，而又是单项链表，不能在O(1)时间内得到被删除结点前面的那一个结点的指针，所以我们原先的方法是不能在O(1)时间内删除结点E的。

那么既然我们不能获得被删除结点的前一个结点的指针，我们就需要转变思路来考虑是否能够用过被删除结点后一个结点的指针来解决方法。因此被删除结点E的后一个结点指针是很容易得到的，也就是E->m_pNext。

那么我们可能会想到如下方法：获得F的指针，将F的数据赋值给E，然后让E指向F的下一个结点。这里虽然删除的是结点F，但是相当于删除的是结点E。并且是O(1)时间复杂度。下面给出代码实例：

View Code

输出结果：

1 2 3 4 5 6 7
1 2 4 5 6 7

 本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2012/04/26/2472102.html，如需转载请自行联系原作者