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

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

思路：题目要求的时间复杂度，迫使我们不得不，开拓思维，另辟蹊径。

代码：

#include<iostream>
using namespace std;
typedef struct ListNode
{
int value;
ListNode* next;
} lnode,*plnode;
plnode head;
plnode todel;
void delNode(plnode head,plnode todel)
{
if(!head||!todel) return;
if(todel->next!=NULL)
{
plnode pNext=todel->next;
todel->value=pNext->value;
todel->next=pNext->next;

delete pNext;
pNext=NULL;
}
else if(head==todel)
{
delete todel;
todel=NULL;
head=NULL;
}
else
{
plnode pNode=head;
while(pNode->next!=todel) pNode=pNode->next;
pNode->next=NULL;
delete todel;
todel=NULL;
}
}
void prtNode(plnode head)
{
plnode node=head;
while(node!=NULL)
{
cout<<node->value<<" ";
node=node->next;
}
cout<<endl;
}
void crelist()
{
head=new lnode;
head->value=0;
head->next=NULL;
int i;
plnode p;
plnode q=head;
for(i=1;i<5;i++)
{
p=new lnode;
p->value=i;
q->next=p;
p->next=NULL;
q=p;
}
todel=p;
}
int main()
{
crelist();
cout<<"before delete"<<endl;
prtNode(head);
delNode(head,todel);
cout<<"after delete"<<endl;
prtNode(head);
return 0;
}

在O(1)时间删除链表节点,布布扣,bubuko.com

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

原文：http://blog.csdn.net/pyz_tech/article/details/23683123