O(1)时间删除链表节点

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

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

前提：默认输入的待删除节点在链表中!

链表结点结构定义如下：

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

思路：若待删结点的下一结点非空，则把它的值复制给待删节点，然后释放待删结点的下一结点；

　　若待删结点的下一结点为空且等于待删结点等于头结点，则释放之；

　　若上面两种情况都不是，即为尾结点，需要从头遍历而后删除；平均时间复杂度[(n-1)*O(1)+O(n)]/n = O(1)

code:

 1 void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
 2 {
 3     if (!pListHead || !pToBeDeleted)
 4     {
 5         return;
 6     }
 7     if (pToBeDeleted->m_pNext != NULL)
 8     {
 9         ListNode* pNext = pToBeDeleted->m_pNext;
10         pToBeDeleted->m_pNext = pNext->m_pNext;
11         pToBeDeleted->m_nValue = pNext->m_nValue;
12         free(pNext);
13         pNext = NULL;
14     } //删除只有一个结点的情况
15     else if(*pListHead == pToBeDeleted)
16     {
17         free(pToBeDeleted);
18         pToBeDeleted = NULL;
19         *pListHead = NULL;
20     }
21     else//删除尾结点
22     {
23         ListNode* pNode = *pListHead;
24         while (pNode->m_pNext != pToBeDeleted)
25         {
26             pNode = pNode->m_pNext;
27         }
28         pNode->m_pNext = NULL;
29         free(pToBeDeleted);
30         pToBeDeleted = NULL;
31     }
32 }