ListCommon.h,ListCommon.cpp依赖：
链表基本操作的函数实现。（1）有这样一个问题，给定一个单向链表的头结点pHead和要删除的节点pDeleted，但是要求在O（1）时间完成。
可能先想到的就是从头结点往前遍历，找到要删除的节点pDeleted，这样就知道了它的前后节点，但是这样的时间是O（n）。
这里的思路是：
把pDeleted的下一个节点pNode1的值赋给pDeleted，同时让pDeleted指向pNode2，然后把pNode1删掉，pDeleted就不删了，这样就不用从头遍历了。
其中有2个特殊情况，1）整个链表只有一个节点，2）要删除的节点是尾节点，这两种情况要特殊处理。
DeleteListNode.cpp
#include <iostream> #include "ListCommon.h" using namespace std; void deleteListNode(ListNode** pHead, ListNode* pDeleted){ if(pHead == NULL || pDeleted == NULL){ return; } cout << "before delete node:"<<endl; PrintList(*pHead); //删除的节点不是头结点，也不是尾节点 if(pDeleted->m_pNext != NULL){ ListNode* pNext = pDeleted->m_pNext; pDeleted->m_nValue = pNext->m_nValue; pDeleted->m_pNext = pNext->m_pNext; delete pNext; pNext = NULL; //删除的是头部节点，这时头结点就被改变了，所以这里的pHead是指向指针的指针。 }else if(*pHead == pDeleted){ delete pDeleted; pDeleted = NULL; pHead = NULL; }else{ //删除的是尾部节点，先找到它的前一个节点，然后把这个pDeleted节点删掉。 ListNode* pNode = *pHead; while(pNode->m_pNext != pDeleted){ pNode = pNode->m_pNext; } pNode->m_pNext = NULL; delete pDeleted; pDeleted =NULL; } cout << "after delete node:"<<endl; PrintList(*pHead); } int main(int argc, char* argv[]){ ListNode* pNode1 = CreateListNode(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ConnectListNodes(pNode1,pNode2); ConnectListNodes(pNode2,pNode3); ConnectListNodes(pNode3,pNode4); ConnectListNodes(pNode4,pNode5); deleteListNode(&pNode1,pNode3); } 测试结果:PC:~/algorithm$ g++ ListCommon.cpp DeleteListNode.cpp -o DeleteListNode PC:~/algorithm$ ./DeleteListNode before delete node: print list begin --- 1 2 3 4 5 print list end after delete node: print list begin --- 1 2 4 5 print list end
