题目：

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

　　链表结点定义如下：

1 struct ListNode{2     int m_nValue;3     ListNode* m_pNext;4 };

1 /*  2     在单链表中删除一个结点，最常规的做法就是从链表的头结点开始， 3     顺序遍历查找要删除的结点，并在链表中删除该结点。 4     但这种思路由于需要顺序查找，时间复杂度为O(n)。 5 */ 6 void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted){ 7     if (pListHead == NULL || pToBeDeleted == NULL) 8         return ; 9     ListNode* pNode = *pListHead;10     if (pNode == pToBeDeleted && pToBeDeleted->m_pNext == NULL){    //链表中只有一个结点11         delete pToBeDeleted;12         pToBeDeleted = NULL;13         pNode = NULL;14     }15     else{16         while(pNode->m_pNext == pToBeDeleted)17             pNode = pNode->m_pNext;18         pNode->m_pNext = pNode->m_pNext->m_pNext;19         delete pToBeDeleted;20         pToBeDeleted = NULL;21     }22 }

1 /* 2     要在O(1)时间删除链表结点，可以将要删除结点的下一个结点的内容复制到 3     需要删除的结点上覆盖原有的内容，再把下一个结点删除。 4     该思路有一个问题：如果要删除的结点位于链表的尾部，则没有下一个结点，怎么办？ 5     此时仍然从链表的头结点开始，顺序遍历得到该结点的前一个结点，并完成删除操作。 6     注：如果链表中只有一个结点，而我们要删除链表的头结点(也是尾结点)， 7     此时我们在删除结点之后，还要把链表的头结点设置为NULL。 8     时间复杂度分析： 9         对于n-1个非尾结点，可以在O(1)时间删除结点；10         对于尾结点而言，由于仍然需要顺序查找，时间复杂度是O(n)。11         因此，总的时间复杂度为：[(n-1)×O(1) + O(n)]/n，结果还是O(1)。12 */13 void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted){14     if (pListHead == NULL || pToBeDeleted == NULL)15         return ;16     if (pToBeDeleted->m_pNext != NULL){    // 要删除的结点不是尾结点17         pToBeDeleted->m_nValue = pToBeDeleted->m_pNext->m_nValue;18         pToBeDeleted->m_pNext = pToBeDeleted->m_pNext->m_pNext;19         delete pToBeDeleted->m_pNext;20         pToBeDeleted->m_pNext = NULL;21     }22     else if (*pListHead == pToBeDeleted){    // 链表中只有一个结点，删除头(尾)结点23         delete pToBeDeleted;24         pToBeDeleted = NULL;25         *pListHead = NULL;26     }27     else{    // 链表中有多个结点，要删除的结点为尾结点，顺序遍历删除尾结点28         ListNode* pNode = *pListHead;29         while (pNode->m_pNext != pToBeDeleted)30             pNode = pNode->m_pNext;31         pNode->m_pNext = NULL;32         delete pToBeDeleted;33         pToBeDeleted = NULL;34     }35 }