循环单链表中间插入节点位置错误，请求代码问题排查

问题描述 #

正在学习链表，解决循环单链表中间插入节点问题时遇到错误，负责插入的函数为add_node_in_bet，代码无法将节点插入正确位置。当前代码如下：

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

struct node
{
    struct node *next;
    int data;
};

void addTOend(struct node **tail, int info)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = info;
    if (*tail == NULL)
    {
        *tail = temp;
        (*tail)->next = (*tail);
    }
    else
    {
        temp->next = (*tail)->next;
        (*tail)->next = temp;
        *tail = temp;
    }
}

void add_node_in_bet(struct node **tail, int info, int pos)
{
    struct node *new = (struct node *)malloc(sizeof(struct node *));
    struct node *p = (*tail)->next;
    new->data = info;
    if (p == *tail)
    {
        new->next = (*tail)->next;
        (*tail)->next = new;
        (*tail) = new;
    }
    else if (p == (*tail)->next)
    {
        new->next = p;
        (*tail)->next= new;
    }
    else
    {
        while (pos > 2)
        {
            p = p->next;
            pos--;
        }
        new->next = p->next;
        p->next = new;
    }
}

void print(struct node **tail)
{
    struct node *p;
    p = (*tail)->next;
    do
    {
        printf("%d ", p->data);
        p = p->next;
    }
    while (p != (*tail)->next);
}

int main()
{
    struct node *tail = NULL;
    addTOend(&tail, 69);
    addTOend(&tail, 65);
    addTOend(&tail, 19);
    addTOend(&tail, 67);
    addTOend(&tail, 68);
    addTOend(&tail, 61);
    addTOend(&tail, 64);
    add_node_in_bet(&tail, 0, 2);
    print(&tail);
}

当前代码输出：

0 69 65 19 67 68 61 64 

问题分析 #

1. 内存分配错误：malloc(sizeof(struct node *))仅分配了指针大小的内存，实际需要分配整个节点的内存，应改为malloc(sizeof(struct node))，否则会导致内存越界或数据损坏。
2. 逻辑判断错误：第二个else if条件p == (*tail)->next永远为真（因为p初始值就是(*tail)->next），导致所有非单节点的插入操作都进入该分支，直接将新节点插入到头部之前，成为新的头节点，这就是输出中0在最前面的原因。
3. 边界处理缺失：未处理空链表的情况，也未正确区分插入位置为头部、中间、尾部的逻辑。

修复后的代码 #

修正add_node_in_bet函数，并完善边界处理：

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

struct node
{
    struct node *next;
    int data;
};

void addTOend(struct node **tail, int info)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = info;
    if (*tail == NULL)
    {
        *tail = temp;
        (*tail)->next = (*tail);
    }
    else
    {
        temp->next = (*tail)->next;
        (*tail)->next = temp;
        *tail = temp;
    }
}

void add_node_in_bet(struct node **tail, int info, int pos)
{
    // 处理空链表情况
    if (*tail == NULL)
    {
        struct node *new_node = (struct node *)malloc(sizeof(struct node));
        new_node->data = info;
        *tail = new_node;
        new_node->next = new_node;
        return;
    }

    struct node *new_node = (struct node *)malloc(sizeof(struct node));
    struct node *p = (*tail)->next;
    new_node->data = info;

    // 单节点情况
    if (p == *tail)
    {
        new_node->next = p;
        (*tail)->next = new_node;
        *tail = new_node;
        return;
    }

    // 插入到头部（pos=1）
    if (pos == 1)
    {
        new_node->next = p;
        (*tail)->next = new_node;
        return;
    }

    // 插入到中间或尾部
    int count = 1;
    // 找到目标位置的前驱节点，循环到count=pos-1
    while (count < pos - 1 && p != *tail)
    {
        p = p->next;
        count++;
    }

    new_node->next = p->next;
    p->next = new_node;

    // 如果插入的是尾部，更新tail指针
    if (p == *tail)
    {
        *tail = new_node;
    }
}

void print(struct node **tail)
{
    if (*tail == NULL)
    {
        printf("链表为空\n");
        return;
    }
    struct node *p = (*tail)->next;
    do
    {
        printf("%d ", p->data);
        p = p->next;
    } while (p != (*tail)->next);
    printf("\n");
}

int main()
{
    struct node *tail = NULL;
    addTOend(&tail, 69);
    addTOend(&tail, 65);
    addTOend(&tail, 19);
    addTOend(&tail, 67);
    addTOend(&tail, 68);
    addTOend(&tail, 61);
    addTOend(&tail, 64);
    add_node_in_bet(&tail, 0, 2);
    print(&tail);
}

修复后输出 #

69 0 65 19 67 68 61 64 

内容的提问来源于stack exchange，提问作者Prashant mourya