面试题：在O(1)时间删除链表结点题目：给定单向

参考答案:

正确答案：

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