​​​​​​​C语言实现单链表基本操作方法

下面是C语言实现单链表基本操作方法的完整攻略：

1. 定义单链表结构体

首先，需要定义一个单链表结构体，来描述节点的信息。结构体应该包含两个部分：数据域和指针域。数据域存储节点的值，指针域存储指向下一个节点的指针。

struct ListNode {
    int val;                // 数据域，此处数据类型为 int
    struct ListNode *next;  // 指针域，指向下一个节点
};

2. 添加节点

添加节点是单链表的最基本操作。我们需要定义一个函数来实现添加节点的功能。

首先，我们需要创建一个新节点，并为它分配内存空间。然后，根据需求将新节点插入到链表中，这需要找到要插入的位置，即要插入节点的前一个节点。最后，将新节点插入到链表中，并调整前一个节点和后一个节点的指针。

void insertNode(struct ListNode **head, int val) {
    // 创建新节点，并为其分配内存空间
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;

    // 特判链表为空的情况
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    // 找到要插入的位置，即要插入节点的前一个节点
    struct ListNode* prev = NULL;
    struct ListNode* curr = *head;
    while (curr && curr->val < val) {
        prev = curr;
        curr = curr->next;
    }

    // 将新节点插入到链表中
    if (prev == NULL) {
        // 如果要插入到链表头部
        newNode->next = *head;
        *head = newNode;
    } else {
        // 如果要插入到链表中间或尾部
        newNode->next = prev->next;
        prev->next = newNode;
    }
}

上述函数中，使用了一个双重指针的技巧，用来修改头结点。具体实现过程如下：

struct ListNode* head = NULL;
...
insertNode(&head, 3);

3. 删除节点

删除节点是单链表的另一个基本操作。我们也需要定义一个函数来实现删除节点的功能。

在删除节点之前，我们需要首先找到要删除的节点，即要删除节点的前一个节点。然后，将前一个节点的指针指向要删除节点的下一个节点，再将要删除节点的空间释放。

void deleteNode(struct ListNode **head, int val) {
    // 特判链表为空的情况
    if (*head == NULL) {
        return;
    }

    // 特判要删除的节点为头结点的情况
    if ((*head)->val == val) {
        struct ListNode* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }

    // 找到要删除的节点，即要删除节点的前一个节点
    struct ListNode* prev = NULL;
    struct ListNode* curr = *head;
    while (curr && curr->val != val) {
        prev = curr;
        curr = curr->next;
    }

    // 删除节点，并释放空间
    if (curr) {
        prev->next = curr->next;
        free(curr);
    }
}

上述函数中也使用了双重指针的技巧。

示例说明

下面通过两个示例来说明如何使用上述函数操作单链表。

示例1：添加节点

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

struct ListNode {
    int val;
    struct ListNode *next;
};

void insertNode(struct ListNode **head, int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct ListNode* prev = NULL;
    struct ListNode* curr = *head;
    while (curr && curr->val < val) {
        prev = curr;
        curr = curr->next;
    }
    if (prev == NULL) {
        newNode->next = *head;
        *head = newNode;
    } else {
        newNode->next = prev->next;
        prev->next = newNode;
    }
}

int main() {
    struct ListNode* head = NULL;
    insertNode(&head, 3);
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 4);
    insertNode(&head, 5);
    struct ListNode* curr = head;
    while (curr) {
        printf("%d ", curr->val);
        curr = curr->next;
    }
    return 0;
}

输出结果为：1 2 3 4 5。

示例2：删除节点

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

struct ListNode {
    int val;
    struct ListNode *next;
};

void insertNode(struct ListNode **head, int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct ListNode* prev = NULL;
    struct ListNode* curr = *head;
    while (curr && curr->val < val) {
        prev = curr;
        curr = curr->next;
    }
    if (prev == NULL) {
        newNode->next = *head;
        *head = newNode;
    } else {
        newNode->next = prev->next;
        prev->next = newNode;
    }
}

void deleteNode(struct ListNode **head, int val) {
    if (*head == NULL) {
        return;
    }
    if ((*head)->val == val) {
        struct ListNode* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    struct ListNode* prev = NULL;
    struct ListNode* curr = *head;
    while (curr && curr->val != val) {
        prev = curr;
        curr = curr->next;
    }
    if (curr) {
        prev->next = curr->next;
        free(curr);
    }
}

int main() {
    struct ListNode* head = NULL;
    insertNode(&head, 3);
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 4);
    insertNode(&head, 5);
    deleteNode(&head, 3);
    deleteNode(&head, 1);
    struct ListNode* curr = head;
    while (curr) {
        printf("%d ", curr->val);
        curr = curr->next;
    }
    return 0;
}

输出结果为：2 4 5。