单向链表节点的删除

单向链表的创建在这里不在赘述，详细请看另一篇文章《单向链表的创建》。在本篇文章中，主要通过举例的方式来帮大家理解单向链表节点的删除。

本篇文章中创建节点用如下表示

typdef struct node{ int date;//定义数据域 struct node * next;//定义指针域 } ElemSN;

在链表节点的删除中，可以分为两种情况

①删除头节点

pDel=head；//定义指针指向待删节点 head=head->next;//挪动头指针 free(pDel);//释放待删除指针完成删除 pDel=NULL;//原指针指空

②删除中间节点、尾节点

q->next=pDel->next;//q为待删除节点的前驱节点指针，pDel为待删除节点指针 free(pDel); pDel=NULL;

删除目标节点可概括为两步：

查找目标节点、删除

例一：设head指向一个非空单向链表、其数据域的值不重复，在链表中删除关键字为key的节点

ElemSN *DelKeyNode(ElemSN *head,int key) {     ElemSN *p,*q;     for(p=head,q=NULL;p&&p->data!=key;q=p;p=p->next);//两指针连动，p指向待删除节点，q指向其前驱节点     if(!p)         printf("NOT FOUND");     else{         if(p==head)             head=head->next;         else             q->next=p->next;         free(p);         p=NULL;     }     return head; }

例二：设数据域值不重复

            ①删除链表中最大值节点

ElemSN *DelMaxNode(ElemSN *head) {     ElemSN *qmax,*pmax,*p;     for(pmax=p=head;p;p=p->next)         if(pmax->data<p->data)             pmax=p;     if(pmax!=head){         for(qmax=head;qmax->next!=pmax;qmax=qmax->next);         qmax->next=pmax->next;     }     else         head=head->next;     pmax->next=NULL;     free(pmax);     return head; }

        ②将链表中最大值节点移动到尾部

ElemSN *MovMaxNodeToTail(ElemSN *head) {     ElemSN *qmax,*pmax,*p;     for(pmax=p=head;p;p=p->next)         if(pmax->data<p->data)             pmax=p;     for(p=head;p->next;p=p->next);     if(pmax!=head){         for(qmax=head;qmax->next!=pmax;qmax=qmax->next);         qmax->next=pmax->next;     }     else         head=head->next;     pmax->next=NULL;     p->next=pmax;     return head; }

例三：设数据域值重复，删除关键值为key的节点

ElemSN *DelKeyNode（ElemSN *head,int key） {     ElemSN *q,*p;     p=head;     while(p){         if(p->data!=key){             q=p;             p=p->next;         }         else{             if(p==head){                 head=head->next;                 free(p);                 p=head             }             else{                 q->next=p->next;                 free(p);                 p=q->next;             }                    }     return head; }

例四：：设head指向一个非空单向链，数据域值重复，且升序有序，删除链表中重复值的节点

void DelNodes(ElemSN *head) {     ElemSN *q,*p;     q=head;     p=head->next;     while(p){         if(p->data==q->data){             q->next=p->next             free(p);             p=q->next;         }         else{             q=p;             p=p->next;         }     } }

例五：设head指向一个非空单向链表，数据域的值重复且无序，删除重复值节点

void DelSameNodes(ElemSN *head) {     ElemSN *p,*q,*pkey;     pkey=head;     while(pkey){         q=pkey;         p=q->next;         while(p){             if(pkey==p){                 q->next=p->next;                 free(p);                 p=q->next;             }             else{                 q=p;                 p=p->next;             }         }         pkey=pkey->next;     } }