作者：解学武

向现有链表中插入结点，根据插入位置的不同，可分为以下 3 种情况：

1. 插入到链表的头部，作为新的链表中第一个存有数据的结点（又称为”首元结点”）；
2. 插入到链表中某两个结点之间的位置；
3. 插入到链表的最末端的位置；

使用头插法和尾插法可分别解决第 1 和第 3 种情况，但是无法解决第 2 种情况，所以本节给大家一段通用代码，可有效解决所有链表结点插入的问题。

无论插入结点位于链表的哪一位置，都可分为两步处理：

1. 将新结点的 next 指针指向插入位置后的结点；
2. 将插入位置前的结点的 next 指针指向该插入结点；

所以，实现结点插入的关键是：在链表中找到新结点要插入的位置，即找到插入位置的上一个结点和下一个结点。找到后，按照以上 2 步即可实现链表的插入。

使用通用代码实现结点插入的前提是：链表中要含有头结点，否则在链表头部插入结点时会出错。

链表插入结点的通用代码（带有详细解析）

#include <stdio.h>
#include <stdlib.h>
typedef struct Link{
    int  elem;
    struct Link *next;
}link;
link * initLink();
//链表插入的函数，p是链表，elem是插入的结点的数据域，add是插入的位置
link * insertElem(link * p,int elem,int add);
void display(link *p);
int main() {
    //初始化链表（1，2，3，4）
    printf("初始化链表为：\n");
    link *p=initLink();
    display(p);

    printf("在第4的位置插入元素5：\n");
    p=insertElem(p, 5, 4);
    display(p);
    return 0;
}
link * initLink(){
    link * p=(link*)malloc(sizeof(link));//创建一个头结点
    link * temp=p;//声明一个指针指向头结点，用于遍历链表
    //生成链表
    for (int i=1; i<5; i++) {
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        temp->next=a;
        temp=temp->next;
    }
    return p;
}
link * insertElem(link * p,int elem,int add){
    link * temp=p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (int i=1; i<add; i++) {
        if (temp==NULL) {
            printf("插入位置无效\n");
            return p;
        }
        temp=temp->next;
    }
    //创建插入结点c
    link * c=(link*)malloc(sizeof(link));
    c->elem=elem;
    //向链表中插入结点
    c->next=temp->next;
    temp->next=c;
    return  p;
}
void display(link *p){
    link* temp=p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null，就执行输出语句。
    while (temp->next) {
        temp=temp->next;
        printf("%d",temp->elem);
    }
    printf("\n");
}

运行结果：
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。