在O(1)时间删除链表结点——13-创新互联
给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点。
成都创新互联于2013年开始,先为樊城等服务建站,樊城等地企业,进行企业商务咨询服务。为樊城企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。因为要求时间复杂度为O(1),所以肯定不能遍历链表,那样的话时间复杂度就是O(N)了;可以想到,其实要求删除该结点,真正的目的并不是要将结点的数据包括结点所占的内存都给删除,只是想让数据消失就可以了,至于结点,除去任意一个结点所占的空间都是OK的;
所以,这里换一种思路,若要删除指定的结点,一般需要将前一个结点的next指针指向要删除结点的下一个结点,这样要删除的结点就可以脱离链表而被删除了,但这里关键就是即是单链表没有prev的指针也没办法遍历链表找到前一个结点,但是可以知道要删除结点的下一个结点和下下个结点啊,因此可以用代替删除法,用下一个结点来代替要删除的结点去“死”,而二者的数据只需要交换一下就可以了,因此删除的结点位置不过是下一个结点,而数据还是要删除的数据;
程序设计如下:
#include#include using namespace std; template struct ListNode //链表结点结构体 { T _data; ListNode * _next; }; template ListNode * buy_node(T data) //构建链表结点 { ListNode * tmp = new ListNode ; tmp->_data = data; tmp->_next = NULL; return tmp; } template void init_list(ListNode ** node, T data) //初始化链表 { *node = buy_node(data); } template void push_node(ListNode *& head, T data) //在链表中链入结点 { if(head == NULL) { init_list(&head, data); return; } ListNode * tmp = head; while(tmp->_next != NULL) { tmp = tmp->_next; } tmp->_next = buy_node(data); } template void print_list(ListNode * head) //打印链表 { while(head != NULL) { cout< _data<<"->"; head = head->_next; } cout<<"NULL"< void destroy_list(ListNode *& head) //删除销毁链表 { if(head != NULL) { ListNode * cur = head; ListNode * tmp = head; while(cur != NULL) { tmp = cur; cur = cur->_next; delete tmp; } head = NULL; } } template ListNode * GetNode(ListNode * pHead, size_t n) //获取要删除结点的地址 { assert(pHead); ListNode * tmp = pHead; while(((--n) != 0) && (tmp != NULL)) { tmp = tmp->_next; } if(tmp == NULL) return NULL; else return tmp; } template void DeleteNode(ListNode * pHead, ListNode * dNode) //删除指定结点 { assert(pHead && dNode); if(dNode->_next == NULL) { delete dNode; dNode = NULL; return; } ListNode * tmp = dNode->_next; swap(dNode->_data, tmp->_data); dNode->_next = tmp->_next; delete tmp; tmp = NULL; } int main() { ListNode * list = NULL; push_node(list, 1); push_node(list, 2); push_node(list, 3); push_node(list, 4); push_node(list, 5); push_node(list, 6); push_node(list, 7); push_node(list, 8); push_node(list, 9); cout<<"print list: "; print_list(list); cout<<"delete Node later: "; ListNode * dNode = GetNode(list, 4); DeleteNode(list, dNode); print_list(list); destroy_list(list); return 0; }
运行程序,得结果:
《完》
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
分享名称:在O(1)时间删除链表结点——13-创新互联
转载来于:http://scyanting.com/article/cdihpo.html