链表-链表节点的删除

场景 1

链表无序，有重复节点，删除链表中值为data的节点。
思路：
链表的删除分为“头删”和“中间尾删”

• 头删：头指针后移，释放原来的头结点

  
  

• 中间尾删：定义两个指针p,q,q指向删除的节点，p指向删除节点的前驱，删除q节点时，只需要将前驱指针的指针域指向删除节点的指针域，那么，要删除的节点就会从链表中脱离，释放掉即可。

  
  

code

ElemSN* delNode(ElemSN *head,int data){
    if(NULL==head){
        return NULL;
    }
    ElemSN *p = head, *q = head,*del = NULL;
    while (q) {
        if(q->data==data){
            if(q==head){
                del = q;
                head = head->next;
            }else {
                del = q;
                p->next = q->next;
            }
            free(del);
            q=p->next;
        }else{
            p=q;
            q=q->next;
        }
    }
    return head;
}

场景二

给定链表中指定节点的地址，从链表中删除该节点
思路：
上面说过，链表分为头删和中间尾删，中间尾删出现的原因就是因为删除节点必须知道他的前驱节点是谁，因为如果不知道，直接删除链表中的节点，那么该链表将会“断开”，本题中，给定的是链表中的指定节点的地址，但是没有给删除节点的前驱，但是，如果要删除的节点为中间节点，我们可以采用偷梁换柱的形式，将要删除的节点的数据域替换成他的下一个节点，这样，他的下一个节点的前驱是刚刚要删除的节点，然后删除掉下一个节点即可。但是如果要删除的节点是尾节点，那么只能通过遍历找到删除节点的前驱，然后进行删除。
整理一下：

1. 如果给定的节点是头节点，头指针后移，释放掉要删除的节点即可
2. 如果给定的节点是链表中间的某一个节点，将该节点的数据域复制成下一个节点的数据域，删除掉下一个节点。

3. 如果给定的节点是尾结点，遍历整个链表，找到尾结点前驱，删除尾结点。
   eg:
   对删除的中间节点的场景举例：

   
   

code

ElemSN* delNode1(ElemSN *head,ElemSN *key){
    if(head==NULL||key==NULL){
        return NULL;
    }
    if(key==head){
        key = head;
        head = head->next;
        free(head);
    }else{
        ElemSN *del = NULL;
        if(key->next==NULL){
            ElemSN *p = head;
            while(p->next==key){
                p=p->next;
            }
            del = key;
            p->next = key->next;
        }else{
            key->data = key->next->data;
            del = key->next;
            key->next = key->next->next;
        }
        free(del);
    }
    return head;
}