首页 > 代码库 > 在O(1)时间内删除单向链表结点

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

2024-07-14 02:42:10   219人阅读

原理：
1.若待删结点在单链表中间，则获取结点下一个结点的值，并复制给待删结点，然后删除待删结点的下一个结点。
2.若待删结点在单链表尾部，则顺序遍历单链表，删除。
3.若链表只有一个结点，正是待删结点，则删除之，并修改相关指针。

核心代码：

//在O(1)时间删除结点。注：必须保证pDel为链表中的结点
void DeleteNode(List *list,pNode pDel)
{
	if(*list == NULL || pDel == NULL)
	{
		return;
	}
	//不是最后一个节点
	if(pDel->next != NULL)
	{//复制pDel后边的结点的值，并删除pDel后边的结点
		pNode pTemp = pDel->next;
		pDel->data = http://www.mamicode.com/pTemp->data;>
完整代码：
/*
在O(1)时间内删除单向链表结点
by Rowandjj
2014/7/25
*/
#include<iostream>
using namespace std;
typedef struct _NODE_
{
	int data;
	struct _NODE_ *next;
}Node,*pNode,*List;
void AddToTail(List *list,int data)
{
	pNode pNew = (pNode)malloc(sizeof(Node));
	if(!pNew)
	{
		exit(-1);
	}
	pNew->data = http://www.mamicode.com/data;>


联系
我们