您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
思路:
时间复杂度要求为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; }
结果:
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。