题目要求：
给定链表的头指针和一个结点指针，在O(1)时间删除该结点。
参考资料：剑指offer第13题。
题目分析：
有几种情况：
1.删除的结点是头结点，且链表不止一个结点；
2.删除的结点是头结点，且链表只有一个结点；
3.删除的结点是尾结点，且链表不止一个结点；
4.删除的结点不是头也不是尾结点；
对于第四种情况（普遍情况），见如下图分析：
对于第三种情况，时间复杂度为O(n).其他情况时间复杂度为O(1).则总的平均复杂度为[(n-1)*O(1)+O(n)]/n = O(1).
代码实现：
#include <iostream>
#include <stack> using namespace std; typedef struct ListNode
{
struct ListNode *next;
int data;
}ListNode; void InitList(ListNode **head1,ListNode **toBeDelete);
void DeleteListNode(ListNode **pHead,ListNode *pToBeDelete);
void PrintList(ListNode *list); int main(void)
{
ListNode *h,*toBeDelete; InitList(&h,&toBeDelete);
PrintList(h);
cout <<"删除5" << endl;
DeleteListNode(&h,toBeDelete);
PrintList(h); return ;
}
void PrintList(ListNode *list)
{
while(list!=NULL)
{
cout << list->data << "->"; list = list->next;
}
cout << "NULL";
cout <<endl;
}
void DeleteListNode(ListNode **pHead,ListNode *pToBeDelete)
{
if(!pHead || !(*pHead) || !pToBeDelete)
return ;
//情况1
if(*pHead==pToBeDelete && pToBeDelete->next != NULL)
{
*pHead = pToBeDelete->next;
delete pToBeDelete;
}
//情况4
else if(pToBeDelete->next != NULL)
{
ListNode *pNext = pToBeDelete->next;
pToBeDelete->data = pNext->data;
pToBeDelete->next = pNext->next;
delete pNext;
pNext = NULL;
}
//情况2
else if(*pHead==pToBeDelete)
{
delete pToBeDelete;
pToBeDelete = NULL;
*pHead = NULL;
}
//情况3
else
{
ListNode *pNode = *pHead;
while(pNode->next != pToBeDelete)
pNode = pNode->next;
pNode->next = NULL;
delete pToBeDelete;
pToBeDelete = NULL;
}
}
//head:1-->5-->9-->NULL
void InitList(ListNode **head1,ListNode **toBeDelete)
{
ListNode *tmp = new ListNode;
tmp->data = ;
*head1 = tmp; tmp = new ListNode;
tmp->data = ;
(*head1)->next = tmp;
*toBeDelete = tmp; ListNode *tmp1 = new ListNode;
tmp1->data = ;
tmp1->next = NULL;
tmp->next = tmp1;
}