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

发布时间:2020-06-15 16:47:20 作者:秋笙夏笛
来源:网络 阅读:233


思路:

时间复杂度要求为O(1),已知要删除的节点,可以找到该节点的下一个节点,把下一个节点的相关信息复制到要删除的节点上,删除下一个节点,可以达到题目要求。

注意:删除尾节点时需要遍历一遍,删除头结点时,需要把头结点移到下一个节点。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

struct Listnode
{
	int _value;
	Listnode* _next;
};
void Init(Listnode*& head)
{
	Listnode* cur =head;
	if(cur==NULL)
	{
		cur=(Listnode*)malloc(sizeof(Listnode));
		cur->_next=NULL;
		cur->_value=0;
	}
	head=cur;
}

void push(Listnode*& head,int value)
{
	Listnode* cur =head;

		while(cur->_next)
		{
			cur=cur->_next;
		}
		Listnode* tmp=NULL;
		tmp=(Listnode*)malloc(sizeof(Listnode));
		tmp->_next=NULL;
		tmp->_value=value;
		cur->_next=tmp;
	
		

}
void pop(Listnode* head)
{
	Listnode* cur=head;
	Listnode* prev=NULL;
	while(cur->_next!=NULL)
	{
		prev=cur;
		cur=cur->_next;
	}
	prev->_next=NULL;
	free(cur);
	cur=NULL;
}
void print(Listnode* head)
{
	Listnode* cur=head;
	while(cur)
	{
		printf("%d\n",cur->_value);
		cur=cur->_next;
	}
}
Listnode* Find(Listnode* head,int value)
{
	assert(head);
	Listnode* cur=head;
    while(cur)
	{
		if(cur->_value==value)
		{
			return cur;
		}
		else
		{
			cur=cur->_next;
		}
	}
}
void DeleteNode(Listnode* &head,Listnode* pToBeDeleted)
{
	Listnode* cur=head;
	if(cur==NULL)
	{
		return;
	}
	if(pToBeDeleted==head)
	{
		head=cur->_next;
		free(cur);
		cur=NULL;
		return;
	}
	Listnode* last=pToBeDeleted->_next;
	if(last!=NULL)
	{
		pToBeDeleted->_value=last->_value;
		pToBeDeleted->_next=last->_next;
		free(last);
		last=NULL;
	}
	else    //删除的是尾节点
	{
		Listnode* prev=NULL;
		while(cur->_next!=NULL)
		{
			prev=cur;
			cur=cur->_next;
		}
		prev->_next=NULL;
		free(cur);
		cur=NULL;
	}
}
void test()
{
	Listnode* head=NULL;
	Init(head);
    push(head,1);
	push(head,2);
	push(head,3);
	/*pop(head);*/
	print(head);
	Listnode* tmp=Find(head,1);
	DeleteNode(head,head);
	print(head);

}
int main()
{
	test();
	system("pause");
	return 0;
}

结果:

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

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



推荐阅读:
  1. leetcode--删除链表中的节点
  2. 链表节点的删除(删除重复无序节点)

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

删除 时间 链表

上一篇:如何解决php中mysql乱码

下一篇:flex开发技巧汇总

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》