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

/************************************************************
题目：给定单向链表的头指针和一个节点指针，定义一个函
数在O(1)时间删除该节点。链表节点与函数的定义如下：
struct ListNode
{
	int m_nValue;
	ListNode* m_pNext;
};
void DeleteNode(ListNode** pListNode, ListNode* pToBeDelete);
*************************************************************/
/*解题思路：
可将需要删除的节点的后下一个节点中的内容放到要删除节点中，
然后下一个节点。其效果刚好是把节点i删除。
如果需要删除的是尾节点，只能顺序遍历得到前序节点。
如果只有一个节点，删除后，还要置为NULL
*/
#include <stdio.h>
struct ListNode
{
	int m_nValue;
	ListNode* m_pNext;
};
void DeleteNode(ListNode** pListNode, ListNode* pToBeDelete)
{
	if(!pListNode || !*pListNode || !*pListNode)
		return;
	
	if(pToBeDelete->m_pNext != NULL)//不是尾节点的情况
	{
		ListNode* pNext = pToBeDelete->m_pNext;
		pToBeDelete->m_nValue =pNext->m_nValue;
		pToBeDelete->m_pNext = pNext->m_pNext;
		delete pNext;
		pNext = NULL;
	}
	else if(*pListNode == pToBeDelete)//链表只有一个节点
	{
		delete pToBeDelete;
		pToBeDelete = NULL;
		*pListNode = NULL;
	}
	else	//有多个节点，删除尾节点
	{
		ListNode* pNode = *pListNode;
		while(pNode->m_pNext != pToBeDelete)
		{
			pNode = pNode->m_pNext;
		}
		pNode->m_pNext = NULL;
		delete pToBeDelete;
		pToBeDelete = NULL;
	}
}
//构造链表节点
ListNode* createListNode(int value)
{
	ListNode* pNode = new ListNode();
	pNode->m_nValue = value;
	pNode->m_pNext = NULL;
	return pNode;
}
//连接节点
void connectListNode(ListNode* pNode1,ListNode* pNode2)
{
	if(pNode1)
		pNode1->m_pNext = pNode2;
}
//销毁链表
void deleteList(ListNode* pHead)
{
	if(pHead)
	{
		ListNode* pNode = pHead;
		while(pNode)
		{
			pHead = pHead->m_pNext;
			delete pNode;
			pNode = pHead;
		}
	}
}
void printList(ListNode* pHead)
{
	if(!pHead)
		return;
	ListNode* pNode = pHead;
	while(pNode)
	{
		printf("%d\t",pNode->m_nValue);
		pNode = pNode->m_pNext;
	}
	printf("\n");
}
//单元测试
void test()
{
	ListNode* pNode1 = createListNode(1);
	ListNode* pNode2 = createListNode(2);
	ListNode* pNode3 = createListNode(3);
	ListNode* pNode4 = createListNode(4);

	connectListNode(pNode1,pNode2);
	connectListNode(pNode2,pNode3);
	connectListNode(pNode3,pNode4);

	printList(pNode1);
	DeleteNode(&pNode1,pNode2);	//删除节点
	printList(pNode1);
	DeleteNode(&pNode1,pNode2);
	printList(pNode1);
	DeleteNode(&pNode1,pNode2);	//相当于删除尾节点
	printList(pNode1);
	DeleteNode(&pNode1,pNode1);	//相当于删除只有一个节点的情况
	printList(pNode1);
}
int main()
{
	test();
	return 0;
}


/*
上面总的平均时间复杂度为：[(N-1)*O(1)+O(N)]/N，结果是O(N)
最坏时间复杂度为O(N)
*/

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

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

原文：http://blog.csdn.net/walkerkalr/article/details/20643589