C语言单链表指定节点插入：前插与后插算法解析

单链表指定节点的插入方式

在单链表中，插入操作是基础且高频的需求。根据目标位置的不同，主要分为在指定节点后方插入和在指定节点前方插入两种情况。理解指针指向的变化是正确实现的前提。

第1步：构建基础单链表结构

在进行插入操作前，首先需要定义链表节点的结构体，并初始化一个包含数据的链表作为操作对象。以下代码演示了如何输入数据并构建一个简单的单链表：

#include <bits/stdc++.h>
using namespace std;

typedef struct node
{
    int data;
    struct node *next;
}no;
 
int main()
{
    no *head,*tail,*p,*q;
    head=new no;
    head->next=NULL;
    tail=head;
    int n;
    printf("一共要输入的数：");
    cin>>n;
    int k;
    cin>>k;
    for(int i=0;i<n;i++)
    {
        p=new no;
        p->data=k;
        p->next=NULL;
        tail->next=p;
        tail=p;
        cin>>k;
    }
    // ... 后续插入逻辑 ...

第2步：实现“后插法”——在指定节点后插入新节点

场景描述：假设链表为 1→2→3→4→5，现需在节点 3 之后插入新节点 newNode，最终结果应为 1→2→3→newNode→4→5。

核心逻辑：

1. 找到目标节点：遍历链表，找到 data == targetData 的节点，记为 point。
2. 建立新节点与后继的联系：将 point->next（即原后继节点4的地址）赋给 newNode->next。
   代码：newNode->next = point->next;
3. 更新目标节点的后继指针：将 point->next 指向新节点 newNode。
   代码：point->next = newNode;

关键警示：步骤2和3的顺序绝对不可调换！如果先执行 point->next = newNode，那么原来 point->next 保存的后继节点地址就会丢失，导致链表从该点开始断开。

int insertAfterNode(struct Test* head, struct Test* newNode, int targetData)
{
    struct Test* point = head;
    while(point != NULL)
    {
        if(point->data == targetData)
        {
            // 后插法标准步骤
            newNode->next = point->next;
            point->next = newNode;
            return 1; // 插入成功
        }
        point = point->next;
    }   
    return 0; // 未找到目标节点
}

第3步：实现“前插法”——在指定节点前插入新节点

场景描述：同样以 1→2→3→4→5 为例，现需在节点 3 之前插入新节点 newNode，结果应为 1→2→newNode→3→4→5。

与前插法相比，难点在于需要知道目标节点的前驱节点，或者特殊处理头节点情况。

情况A：目标节点非头节点（正常前插）

我们需要遍历链表，寻找满足 point->next->data == targetData 的节点 point（即目标节点的前驱）。

• 判断条件：使用 while(point->next != NULL) 而非 point != NULL，因为我们要访问 point->next。
• 查找目标：检查 if(point->next->data == targetData)。
• 执行插入：一旦找到前驱 point，操作步骤与后插法类似：
  • newNode->next = point->next; （新节点指向原目标节点3）
  • point->next = newNode; （前驱节点指向新节点）

// 在非头节点处前插
struct Test* insertBeforeNonHead(struct Test *head, struct Test* newNode, int targetData)
{
    struct Test* point = head;
    
    // 遍历寻找前驱节点
    while(point->next != NULL)
    {
        if(point->next->data == targetData)
        {
            newNode->next = point->next;
            point->next = newNode;
            printf("Insert success!\n");
            return head;
        }
        point = point->next;
    }
    printf("Sorry, you find error! (Target not found)\n");
    return head;
}

情况B：目标节点即为头节点

如果需要插入的位置是在第一个节点之前，上述 while(point->next != NULL) 循环无法处理，因为此时没有前驱节点。这种情况下，新节点将成为新的头节点。

// 在头节点处前插
// 注意：此函数通常需结合主调函数判断是否调用
struct Test* insertAtHead(struct Test *head, struct Test* newNode)
{
    if(head == NULL) return newNode;
    
    newNode->next = head;
    return newNode; // 返回新的头指针
}

综合实现建议：在实际编码中，可以先判断目标是否是头节点，如果是，直接调用头插逻辑；如果不是，则调用上述的前插逻辑。

关键注意事项总结

1. 指针操作顺序：无论是前插还是后插，必须先让新节点的 next 指向正确的目标，再修改相关节点的 next，否则会导致链表断裂（Memory Leak/Undefined Behavior）。
2. 头节点变化：如果在头部进行插入（前插法），head 指针的值会改变。因此，包含头节点插入的函数应当 return 新的头指针，并在调用方接收赋值（如 head = insertAtHead(head, newNode);）。
3. 内存管理：实际工程中，动态申请的节点 (malloc/calloc) 需确保在程序退出或链表销毁时释放，避免内存泄漏。

以上就是C语言单链表指定节点插入的详细解析，更多关于数据结构与算法的资料请关注本站其它相关文章！