使用void函数在循环链表头部插入节点的二级指针错误排查

问题背景 #

尝试用void函数实现循环链表头部插入节点，由于需要修改head指针本身，传入了指向指针的指针（二级指针），但标注为"the error is here"的第24行出现错误。此前传入普通指针时，节点会被插入到链表尾部。

错误代码 #

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

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

void circularLLTraversal(struct Node *head)
{
    struct Node *ptr = head;
    do
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    } while (ptr != head);
}

void insertionAtBeginning(struct Node **head, int data)
{
    struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));
    ptr->data = data;
    struct Node *p = *head->next; //The error is here
    while (p->next != *head)
    {
        p = p->next;
    }
    // At this point p points to the last node of the circular linked list

    p->next = ptr;
    ptr->next = *head;
    *head = ptr;
}

int main()
{

    struct Node *head;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;

    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));

    head->data = 4;
    head->next = second;

    second->data = 3;
    second->next = third;

    third->data = 6;
    third->next = fourth;

    fourth->data = 1;
    fourth->next = head;

    printf("Circular Linked List before insertion:\n");
    circularLLTraversal(head);

    insertionAtBeginning(&head, 8);

    printf("Circular Linked List after insertion:\n");
    circularLLTraversal(head);

    return 0;
}

错误原因 #

问题出在运算符优先级：->的优先级高于*，所以*head->next会被编译器解释为*(head->next)。但head是二级指针（struct Node **类型），它本身没有next成员，这直接导致编译错误。

正确的写法应该是先对二级指针head解引用，得到一级指针*head（即链表的头指针），再访问它的next成员，也就是(*head)->next。

修正后的代码 #

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

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

void circularLLTraversal(struct Node *head)
{
    struct Node *ptr = head;
    do
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    } while (ptr != head);
}

void insertionAtBeginning(struct Node **head, int data)
{
    struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));
    ptr->data = data;
    
    // 修正优先级问题：先解引用二级指针，再访问next
    struct Node *p = (*head)->next;
    while (p->next != *head)
    {
        p = p->next;
    }

    p->next = ptr;
    ptr->next = *head;
    *head = ptr;
}

int main()
{

    struct Node *head;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;

    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));

    head->data = 4;
    head->next = second;

    second->data = 3;
    second->next = third;

    third->data = 6;
    third->next = fourth;

    fourth->data = 1;
    fourth->next = head;

    printf("Circular Linked List before insertion:\n");
    circularLLTraversal(head);

    insertionAtBeginning(&head, 8);

    printf("Circular Linked List after insertion:\n");
    circularLLTraversal(head);

    return 0;
}

额外优化建议 #

如果需要兼容空链表的情况，可以在函数开头增加判断：

if (*head == NULL) {
    ptr->next = ptr; // 空链表插入第一个节点，自己指向自己
    *head = ptr;
    return;
}

内容的提问来源于stack exchange，提问作者Neilson Programmer