在O(1) 时间删除链表结点

 1 #include "stdafx.h"
 2 #include <iostream>
 3 /*
 4 题目:在O(1)时间删除链表结点
 5     给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。链表结点与函数定义如下:
 6     struct ListNode
 7     {
 8         int m_nValue;
 9         ListNode *m_pNext;
10     };
11     void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted);
12 */
13 using namespace std;
14 struct ListNode
15     {
16         int m_nValue;
17         ListNode *m_pNext;
18     };
19 void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted)
20 {
21     if (pListHead ==NULL||pToBeDeleted==NULL)
22     {
23         return;
24     }
25     //删除的不是尾结点
26     if(pToBeDeleted->m_pNext!=NULL)
27     {
28         ListNode* pNext = pToBeDeleted->m_pNext;
29         pToBeDeleted->m_nValue=pNext->m_nValue;
30         pToBeDeleted->m_pNext=pNext->m_pNext;
31         delete pNext;
32         pNext=NULL;
33     }
34     //链表只有一个结点
35     else if(*pListHead==pToBeDeleted)
36     {
37         delete pToBeDeleted;
38         pToBeDeleted=NULL;
39         *pListHead = NULL;
40     }
41     //如果要删除的是尾结点
42     else
43     {
44         ListNode* pNode = *pListHead;
45         while(pNode->m_pNext!=pToBeDeleted)
46             pNode=pNode->m_pNext;
47         pNode->m_pNext = NULL;
48         delete pToBeDeleted;
49         pToBeDeleted=NULL;
50     }
51 }
52 
53 
54 int _tmain(int argc, _TCHAR* argv[])
55 { 
56     
57     return 0 ;
58 }