c++语言程序设计习题之用O(1)时间删除单向链表的结点。

本文摘自《剑指Offer》

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

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

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

在单向链表中删除一个结点，最常规的做法是从链表的头结点开始，顺序遍历查找要删除的结点，找到之后再删除。由于需要顺序查找，时间复杂度是O(n) 。

试着换一种思路。找到要删除结点的下一个结点，把下一个结点的m_nValue复制到要删除结点上覆盖原有的内容，然后删除下一个结点，这样就相当于把当前要删除的结点删除了。这样，时间复杂度为O(1)。(因为单向链表的结点中只有m_pNext，而没有m_pPrev)

上面的思路还有一个问题：如果删除的结点位于链表的尾部，没有下一个结点，怎么办？仍然需要从链表的头结点开始，顺便遍历得到给定结点的前序结点，并完成删除操作。此时的时间复杂度是O(n)。

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

void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
if (!pListHead || !pToBeDeleted)
return;

// 要删除的结点不是尾结点
if(pToBeDeleted->m_pNext != NULL)
{
ListNode* pNext = pToBeDeleted->m_pNext;
pToBeDeleted->m_nValue = pNext->m_nValue;
pToBeDeleted->m_pNext = pNext->m_pNext;

delete pNext;
pNext = NULL;
}
// 链表只有一个结点，删除头结点（也是尾结点）
else if(*pListHead == pToBeDeleted)
{
delete pToBeDeleted;
pToBeDeleted = NULL;
*pListHead = NULL;
}
// 链表中有多个结点，删除尾结点
else
{
ListNode* pNode = *pListHead;
while(pNode->m_pNext != pToBeDeleted)
{
pNode = pNode->m_pNext;
}

pNode->m_pNext = NULL;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}

对于n-1个非尾结点而言，可以在O(1)时间把下一个结点的内容复制到要删除的结点，并删除下一个结点；对于尾结点而言，仍然需要顺序查找，时间复杂度是O(n)。总的平均时间复杂度是 [(n-1)*O(1)+O(n)]/n，结果还是O(1)，满足题目要求。

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