【面试题】剑指offer 13

在O（1）时间删除链表节点

listnode.h

#include<iostream>#include<cassert>using namespace std;struct ListNode{	int _value;	ListNode* pNext;};class List{public:	List()		:pHead(NULL)	{}	~List()	{		delete pHead;		pHead=NULL;	}	void deleteNode(ListNode* todelete)	{		assert(todelete);		if (todelete->pNext!=NULL)		{			ListNode* next=todelete->pNext;			todelete->_value=next->_value;			todelete->pNext=next->pNext;			delete next;			next=NULL;		}		else if(pHead==todelete)		{			delete todelete;			todelete=NULL;			pHead=NULL;		}		else		{			ListNode* node=pHead;			while (node->pNext!=todelete)			{				node=node->pNext;			}			node->pNext=NULL;			delete todelete;			todelete=NULL;		}	}	void addNode(const int value)	{			ListNode* newnode=new ListNode();	        if (pHead==NULL)	        {				newnode->_value=value;				newnode->pNext=NULL;				pHead=newnode;				return;	        }			ListNode* node=pHead;			while(node->pNext!=NULL)			{				node=node->pNext;			}			newnode->_value=value;			newnode->pNext=NULL;			node->pNext=newnode;			}	void PRintNodeValue()	{		ListNode* node=pHead;		while (node)		{			cout<<node->_value<<" ";			node=node->pNext;		}		cout<<endl;	}ListNode* Find(const int x){	ListNode* node=new ListNode();	node=pHead;	while (node)	{		if(node->_value==x)		break;		node=node->pNext;	}	return node;}ListNode* getHead(){	return pHead;}private:	ListNode* pHead;};void test(){	List l;	l.addNode(1);	l.addNode(2);	l.addNode(3);	l.addNode(4);	l.addNode(5);	l.addNode(6);	l.addNode(7);	l.addNode(8);	l.addNode(9);	l.printNodeValue();	l.deleteNode(l.Find(5));	l.printNodeValue();}test.c
#include "ListNode.h"int main(){	test();	system("pause");	return 0;}