3、单向链表的插入操作：头插法、尾插法、指定位置插入

链表插入，说白了就是往链子里塞新节点。但往哪塞、怎么塞，这里头讲究不少。我刚开始写链表时，总觉得插入不就是改几个指针嘛，结果一跑就段错误。后来才明白，每种插入方式都有自己的脾气。

单向链表的插入，按位置分三种：头插法、尾插法、指定位置插入。这三种方式，你在项目中几乎都会用到。比如我去年做的一个嵌入式日志系统，头插法用来存最新日志，尾插法用来维护FIFO队列，指定位置插入则用在优先级任务链表中。

3.1 头插法：新节点永远站在C位

头插法，就是把新节点插到链表的最前面。新节点成为新的头节点，原来的头节点往后挪一位。

你想想看，这像什么？像排队时有人插队到最前面。后面的人全得往后挪一步。

// 头插法：在链表头部插入新节点
Node* insertAtHead(Node* head, int data) {
    // 1. 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    newNode->data = data;
    
    // 2. 新节点指向当前头节点
    newNode->next = head;
    
    // 3. 更新头指针
    head = newNode;
    
    return head;
}

头插法的时间复杂度是O(1)，非常快。但要注意，插入顺序和链表顺序是相反的。你按1、2、3的顺序头插，链表里存的是3、2、1。

3.2 尾插法：新节点乖乖排到队尾

尾插法，就是把新节点加到链表末尾。这符合我们日常的排队习惯——新人站最后。

尾插法需要先找到链表的最后一个节点，然后把新节点接上去。这里有个特殊情况：如果链表是空的，那尾插法其实就变成了头插法。

// 尾插法：在链表尾部插入新节点
Node* insertAtTail(Node* head, int data) {
    // 1. 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    newNode->data = data;
    newNode->next = NULL;
    
    // 2. 如果链表为空，新节点就是头节点
    if (head == NULL) {
        return newNode;
    }
    
    // 3. 遍历找到最后一个节点
    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    
    // 4. 最后一个节点指向新节点
    temp->next = newNode;
    
    return head;
}

尾插法的时间复杂度是O(n)，因为要遍历到链表末尾。如果频繁做尾插，可以考虑维护一个尾指针，这样就能降到O(1)。

3.3 指定位置插入：精准打击

指定位置插入，就是插到链表的第pos个位置。这个最灵活，但也最容易出错。

为什么？因为你要处理三种情况：

• pos=0：相当于头插法
• pos=链表长度：相当于尾插法
• pos在中间：需要找到pos-1位置的节点，然后修改指针

// 指定位置插入：在第pos个位置插入新节点（pos从0开始）
Node* insertAtPosition(Node* head, int data, int pos) {
    // 1. 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    newNode->data = data;
    
    // 2. 头插情况
    if (pos == 0) {
        newNode->next = head;
        return newNode;
    }
    
    // 3. 找到第pos-1个节点
    Node* temp = head;
    int i = 0;
    while (temp != NULL && i < pos - 1) {
        temp = temp->next;
        i++;
    }
    
    // 4. 检查位置是否有效
    if (temp == NULL) {
        printf("位置%d无效，超出链表范围\n", pos);
        free(newNode);
        return head;
    }
    
    // 5. 插入新节点
    newNode->next = temp->next;
    temp->next = newNode;
    
    return head;
}

3.4 三种插入方式对比

插入方式	时间复杂度	空间复杂度	适用场景	注意事项
头插法	O(1)	O(1)	需要逆序存储、栈结构	必须更新头指针
尾插法	O(n)	O(1)	FIFO队列、顺序存储	新节点next要置NULL
指定位置插入	O(n)	O(1)	有序链表、优先级队列	检查位置有效性

3.5 插入操作的完整示例

下面是一个完整的示例，把三种插入方式串起来跑一遍：

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 打印链表
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    Node* head = NULL;
    
    // 头插法：插入3, 2, 1
    head = insertAtHead(head, 1);
    head = insertAtHead(head, 2);
    head = insertAtHead(head, 3);
    printf("头插法结果: ");
    printList(head);  // 输出: 3 -> 2 -> 1 -> NULL
    
    // 尾插法：插入4, 5
    head = insertAtTail(head, 4);
    head = insertAtTail(head, 5);
    printf("尾插法结果: ");
    printList(head);  // 输出: 3 -> 2 -> 1 -> 4 -> 5 -> NULL
    
    // 指定位置插入：在位置2插入100
    head = insertAtPosition(head, 100, 2);
    printf("指定位置插入结果: ");
    printList(head);  // 输出: 3 -> 2 -> 100 -> 1 -> 4 -> 5 -> NULL
    
    return 0;
}

3.6 插入操作的核心流程图

下面这张图，把三种插入方式的流程都画出来了。我建议你仔细看看，特别是指针变化的那几步。

3.7 常见错误与避坑指南

好了，单向链表的插入操作就讲到这里。这三种插入方式，你写代码时几乎天天都会用到。头插法快但顺序反，尾插法慢但顺序正，指定位置插入最灵活但要注意边界。记住这些特点，写代码时心里就有数了。

---

公众号:蓝海资料掘金营，微信deep3321