03 链表的删除：删除链表中与目标值相等的元素（Linked List 链表）

采用C语言完整实现。

原链表为1->2->3，现在要删除与目标值2相等的元素，删除后，链表变为1->3。

#include <stdio.h>
#include <stdlib.h>
#include <MacTypes.h>

/*定义节点*/
typedef struct Node {
    int data;
    struct Node *next;
} LinkedList;

/*使用头插法来构建一个链表*/
void push(struct Node **head_ref, int new_data);

/*给一个指针的指针作为引用，作为这个链表的头指针,进行删除指定位置的节点*/
void deleteNode(struct Node **head_ref, int position);

/*打印链表*/
void printList(LinkedList *node);

int main() {
    LinkedList *head_ref = NULL;
    //注意这里要传取地址符
    push(&head_ref, 3);
    push(&head_ref, 4);
    push(&head_ref, 5);
    deleteNode(&head_ref,2);
    printList(head_ref);
    return 0;
}

/*
 * 头插法的几步
 * 1.定义一个新的指针，给指针申请空间，使其变成一个新的节点。
 * 2.给这个新的节点data数据域赋值。
 * 3.将这个新的节点的next指针指向原来的开始节点（原头指针指向的节点）
 * 4.将原头指针左移移动到新的节点
 */
void push(struct Node **head_ref, int new_data) {

    LinkedList *new_node = (LinkedList *) malloc(sizeof(LinkedList));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

/*从给定节点往后打印链表*/
void printList(LinkedList *node) {
    //节点不为空，循环
    while (node != NULL) {
        //打印节点值
        printf(" %d \n", node->data);
        //指针后移
        node = node->next;
    }
}

/*删除指定位置的的节点*/
void deleteNode(struct Node **head_ref, int position) {

    //1.首先判断这个链表是否为空
    if (*head_ref == NULL) {
        return;
    }

    //2.创建一个指针存储头节点
    struct Node *temp = *head_ref;

    //3.如果这个position是0，那么直接移除掉头节点
    if (position == 0) {
        *head_ref = temp->next;
        free(temp);
        return;
    }

    //4.从头节点遍历，找到删除位置position的前驱节点,temp指向前驱
    for (int i = 0; temp != NULL && i < position - 1; ++i) {
        temp = temp->next;
    }

    //5.如果这个位置比链表还长
    if (temp == NULL || temp ->next == NULL){
        return;
    }

    //6.创建一个新的指针指向将要删除的节点的下一个节点
    //temp是删除节点的前驱
    //temp->next 这个节点是即将被删除的节点
    struct Node *next = temp->next->next;
    //7.删除节点
    free(temp->next);

    //8.将next节点连接在前驱节点temp后面
    temp->next=next;

}

输出：

 3  2  1  3  1