在O(1)时间内删除链表节点详解编程语言

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

【方案】
方案一：从链表头节点开始顺序遍历查找要删除的节点，并在链表中删除该节点，如图A。因为这种思路需要顺序查找，时间复杂度是O(n)，不符合要求。
方案二：把要删除节点的下一个节点的数据覆盖到被删除的节点，然后把下个节点删除掉，如图B。

图1 删除链表节点图

【解题思路】
方案二有三种情况：
1、在多节点链表中，要删除的节点不是尾节点时。如B链表，要删除节点i，先把j节点的数据复制到i节点上，再让i的指针指向j节点的下一个节点，最后把j节点删除掉，就相当于删除了i节点。
2、链表只有一个节点，删除节点（既是头节点，也是尾节点）。在删除节点后，还要把头节点置空。
3、链表有多个节点，删除尾节点。从链表的头节点开始，顺序遍历得到该节点的前序节点，并完成删除操作。

【代码】

//假设要删除的节点存在于链表中 
void DeleteNode(Node** plist, Node* pDeleteNode) 
{ 
	//链表节点为空；要删除的节点为空 
	if (plist == NULL || pDeleteNode == NULL) 
	{ 
		return; 
	} 
 
	//多节点，要删除的节点不是尾节点 
	if(pDeleteNode->next != NULL) 
	{ 
		Node* pnext = pDeleteNode->next; 
		pDeleteNode->data = pnext->data; 
		pDeleteNode->next = pnext->next; 
		delete pnext; 
		pnext = NULL; 
	} 
	 
	//单节点，删除节点（既是头节点又是尾节点） 
	else if (*plist == pDeleteNode) 
	{ 
		delete pDeleteNode; 
		pDeleteNode = NULL; 
		*plist = NULL; 
	} 
 
	//多节点，要删除的节点是尾节点 
	else  
	{ 
		Node* pNode = *plist; 
		while (pNode->next != pDeleteNode) 
		{ 
			pNode = pNode->next; 
		} 
		pNode->next = NULL; 
		delete pDeleteNode; 
		pDeleteNode = NULL; 
	} 
} 

【程序】

#define _CRT_SECURE_NO_WARNINGS 1 
# include <stdio.h> 
# include <stdlib.h> 
# include <assert.h> 
 
typedef int DataType; 
 
typedef struct Node 
{ 
	DataType data; 
	struct Node *next; 
}Node, *pList, *pNode; 
 
void InitLinkList(pList *pplist) 
{ 
	assert(pplist); 
	*pplist = NULL; 
} 
 
void PushBack(pList *pplist, DataType x) 
{ 
	pNode cur = *pplist; 
	pNode pnode = NULL; 
	assert(pplist); 
	pnode = (pNode)malloc(sizeof(Node)); 
	if (pnode == NULL) 
	{ 
		perror("PushBack::malloc"); 
		exit(EXIT_FAILURE); 
	} 
	pnode->data = x; 
	pnode->next = NULL; 
	if (cur == NULL) 
	{ 
		*pplist = pnode; 
	} 
	else 
	{ 
		while (cur->next != NULL) 
		{ 
			cur = cur->next; 
		} 
		cur->next = pnode; 
	} 
} 
 
void Display(pList plist) 
{ 
	pNode cur = plist; 
	while (cur) 
	{ 
		printf("%d-->", cur->data); 
		cur = cur->next; 
	} 
	printf("over/n"); 
} 
 
void PrintNode(pList plist) 
{ 
	assert(plist); 
	pNode cur = plist; 
	if (plist == NULL) 
	{ 
		return; 
	} 
	else 
	{ 
		printf("%d/n", cur->data); 
 
	} 
} 
 
void Destroy(pList *pplist) 
{ 
	pNode cur = *pplist; 
	assert(pplist); 
	while (cur) 
	{ 
		pNode del = cur; 
		cur = cur->next; 
		free(del); 
	} 
	*pplist = NULL; 
} 
 
//假设要删除的节点存在于链表中 
void DeleteNode(Node** plist, Node* pDeleteNode) 
{ 
	//链表节点为空；要删除的节点为空 
	if (plist == NULL || pDeleteNode == NULL) 
	{ 
		return; 
	} 
 
        //多节点，要删除的节点不是尾节点 
        if (pDeleteNode->next != NULL) 
	{ 
		Node* pNext = pDeleteNode->next; 
		pDeleteNode->data = pNext->data; 
		pDeleteNode->next = pNext->next; 
		delete pNext; 
		pNext = NULL; 
	} 
 
       //单节点，删除节点（既是头结点又是尾节点） 
       else if(*plist == pDeleteNode) 
       { 
	       delete pDeleteNode; 
	       pDeleteNode = NULL; 
	       *plist = NULL; 
        } 
 
	//多节点，要删除的节点是尾节点 
	else  
	{ 
		Node* pNode = *plist; 
		while (pNode->next != pDeleteNode) 
		{ 
			pNode = pNode->next; 
		} 
		pNode->next = NULL; 
		delete pDeleteNode; 
		pDeleteNode = NULL; 
	} 
} 
 
void test1() 
{ 
	pList plist1; 
	pNode ret = NULL; 
	InitLinkList(&plist1); 
	PushBack(&plist1, 1); 
	PushBack(&plist1, 2); 
	PushBack(&plist1, 3); 
	PushBack(&plist1, 4); 
	Display(plist1); 
	DeleteNode(&plist1, plist1->next); 
	Display(plist1); 
	Destroy(&plist1); 
} 
 
int main() 
{ 
	test1(); 
	system("pause"); 
	return 0; 
} 

【测试】
1、功能测试
（1）从有多个节点的链表的中间删除一个节点。
（2）从有多个节点的链表中删除头节点。
（3）从有多个节点的链表中删除尾节点。
（4）从只有一个节点的链表中删除节点。
2、特殊功能测试
（1）指向链表的头指针为空。
（2）指向链表要删除节点的指针为空。

运行结果：

注意：要先判断在多节点中删除的节点不是尾节点的情况，再判断在单节点中删除的节点既是头结点又是尾节点的情况。不然，当删除的是多节点的节点是头结点时，就会错误的执行删除单节点的代码！