给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。


因为要求时间复杂度为O(1)，所以肯定不能遍历链表，那样的话时间复杂度就是O(N)了；可以想到，其实要求删除该结点，真正的目的并不是要将结点的数据包括结点所占的内存都给删除，只是想让数据消失就可以了，至于结点，除去任意一个结点所占的空间都是OK的；

所以，这里换一种思路，若要删除指定的结点，一般需要将前一个结点的next指针指向要删除结点的下一个结点，这样要删除的结点就可以脱离链表而被删除了，但这里关键就是即是单链表没有prev的指针也没办法遍历链表找到前一个结点，但是可以知道要删除结点的下一个结点和下下个结点啊，因此可以用代替删除法，用下一个结点来代替要删除的结点去“死”，而二者的数据只需要交换一下就可以了，因此删除的结点位置不过是下一个结点，而数据还是要删除的数据；

程序设计如下：

#include<iostream>#include<assert.h>usingnamespacestd;template<classT>structListNode//链表结点结构体{T_data;ListNode<T>*_next;};template<classT>ListNode<T>*buy_node(Tdata)//构建链表结点{ListNode<T>*tmp=newListNode<T>;tmp->_data=data;tmp->_next=NULL;returntmp;}template<classT>voidinit_list(ListNode<T>**node,Tdata)//初始化链表{*node=buy_node(data);}template<classT>voidpush_node(ListNode<T>*&head,Tdata)//在链表中链入结点{if(head==NULL){init_list(&head,data);return;}ListNode<T>*tmp=head;while(tmp->_next!=NULL){tmp=tmp->_next;}tmp->_next=buy_node(data);}template<classT>voidprint_list(ListNode<T>*head)//打印链表{while(head!=NULL){cout<<head->_data<<"->";head=head->_next;}cout<<"NULL"<<endl;}template<classT>voiddestroy_list(ListNode<T>*&head)//删除销毁链表{if(head!=NULL){ListNode<T>*cur=head;ListNode<T>*tmp=head;while(cur!=NULL){tmp=cur;cur=cur->_next;deletetmp;}head=NULL;}}template<classT>ListNode<T>*GetNode(ListNode<T>*pHead,size_tn)//获取要删除结点的地址{assert(pHead);ListNode<T>*tmp=pHead;while(((--n)!=0)&&(tmp!=NULL)){tmp=tmp->_next;}if(tmp==NULL)returnNULL;elsereturntmp;}template<classT>voidDeleteNode(ListNode<T>*pHead,ListNode<T>*dNode)//删除指定结点{assert(pHead&&dNode);if(dNode->_next==NULL){deletedNode;dNode=NULL;return;}ListNode<T>*tmp=dNode->_next;swap(dNode->_data,tmp->_data);dNode->_next=tmp->_next;deletetmp;tmp=NULL;}intmain(){ListNode<int>*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<<"printlist:";print_list(list);cout<<"deleteNodelater:";ListNode<int>*dNode=GetNode(list,4);DeleteNode(list,dNode);print_list(list);destroy_list(list);return0;}


运行程序，得结果：



《完》