13 在O1的时间删除链表节点

发布时间:2017-2-26 10:54:27编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"13 在O1的时间删除链表节点",主要涉及到13 在O1的时间删除链表节点方面的内容,对于13 在O1的时间删除链表节点感兴趣的同学可以参考一下。


题目描述:给定单向链表的头指针和一个节点指针,定义一个函数在O(1)的时间删除该节点。链表节点与函数的定义如下:

struct ListNode
{
int m_nValue;
ListNode *m_pNext;
};
void deleteNode(ListNode *pListHead,ListNode *pDelete);

分析: 使用一个节点指针,删除某一个指定节点,在删除某节点的时候需要前面一个节点的后驱指针,在只有有一个节点的情况下,没有办法获得。

那么,我们只有考虑把所要删除节点的后一个节点的内容复制到被删除节点,再删除后驱的一个节点,即可满足。


struct ListNode
{
	int m_nValue;
	ListNode *m_pNext;
};
void deleteNode(ListNode *pListHead,ListNode *pDelete);
int main(int argc, char* argv[])
{
	printf("Hello World!\n");
	return 0;
}

void deleteNode(ListNode **pListHead,ListNode *pDelete)
{
	if(!pListHead||!pDelete)
		return;
	//删除的不是尾节点
	if(pDelete->m_pNext!=NULL)
	{
		ListNode *pNext = pDelete->m_pNext;
		pDelete->m_nValue=pNext->m_nValue;
		pDelete->m_pNext=pNext->m_pNext;
		delete pNext;
		pNext = NULL;
	}else
		if(*pListHead==pDelete)
		{
			delete pDelete;

			pDelete=NULL;
			*pListHead=NULL;
		}
		else   //删除尾节点
		{
			ListNode *pNode = *pListHead;
			while(pNode->m_pNext!=pDelete)
			{
				pNode = pNode->m_pNext;
			}
			pNode->m_pNext=NULL;
			delete pDelete;
			pDelete = NULL;
		}
}





上一篇:IIS与tomcat共用80端口方法3
下一篇:x264源代码 概述 框架分析 架构分析

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款