单链表尾节点有效值检查方法及push操作通用实现方案咨询

在单链表的push函数实现中，有时会考虑这样的场景：如果链表存在一个尚未赋值的尾节点，就直接给这个节点赋值，而不是新建节点；其他情况则创建新节点后再赋值。但这里的核心问题是——如何可靠判断尾节点是否为未使用的状态？用特殊值（比如示例中的98989）的方案不仅容易和业务数据冲突，还无法兼容外部传入的链表，有没有业内通用的处理方式？

以下是我当前的实现代码，但这个方案实用性很差：

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

struct ListNode
{
    int val;
    struct ListNode *next;
};

void linked_init(struct ListNode **p)
{
    (*(p)) = malloc(sizeof(struct ListNode));
    (*(p))->next = NULL;
    // 为尾节点分配一个"唯一标识值"，表示该节点尚未被赋予有效值
    (*(p))->val = 98989;
}

void linked_push(struct ListNode **p, int curval)
{
    // 判断是否是未使用的尾节点
    if ((*(p))->next == NULL && (*(p))->val == 98989)
    {
        // 直接给已有尾节点赋值
        (*(p))->val = curval;
    }
    else
    {
        // 创建新节点并插入（这里是头插）
        struct ListNode *temp;
        temp = malloc(sizeof(struct ListNode));
        temp->val = curval;
        temp->next = (*(p));
        (*(p)) = temp;
    }
}

void linked_display(struct ListNode *p)
{
    struct ListNode *temp;
    temp = p;
    while (temp)
    {
        printf("%d\n", (temp)->val);
        temp = temp->next;
    }
}

int main(int argc, char **argv)
{
    struct ListNode *list;
    linked_init(&list);

    // 首次push会复用初始化的尾节点，但这种方式只适用于自己创建的链表
    linked_push(&list, 14);
    linked_push(&list, 17);
    linked_push(&list, 20);
    linked_push(&list, 90);

    linked_display(list);

    return 0;
}

业内通用的处理方式 #

1. 用NULL表示空链表，避免预分配节点 #

这是最常见的方案：空链表直接用NULL标识，push时判断链表是否为空：

• 如果是空链表，创建第一个节点作为头节点；
• 如果非空，创建新节点并插入（头插、尾插根据需求选择）。

这种方式不需要依赖特殊值，也能兼容所有标准链表结构，示例代码：

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

struct ListNode
{
    int val;
    struct ListNode *next;
};

// 初始化空链表
void linked_init(struct ListNode **p)
{
    *p = NULL;
}

// 头插式push
void linked_push(struct ListNode **p, int curval)
{
    struct ListNode *temp = malloc(sizeof(struct ListNode));
    temp->val = curval;
    temp->next = *p;
    *p = temp;
}

// 尾插式push（需要遍历到尾部）
void linked_push_tail(struct ListNode **p, int curval)
{
    struct ListNode *new_node = malloc(sizeof(struct ListNode));
    new_node->val = curval;
    new_node->next = NULL;

    if (*p == NULL)
    {
        *p = new_node;
        return;
    }

    struct ListNode *temp = *p;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = new_node;
}

void linked_display(struct ListNode *p)
{
    struct ListNode *temp = p;
    while (temp)
    {
        printf("%d\n", temp->val);
        temp = temp->next;
    }
}

int main()
{
    struct ListNode *list;
    linked_init(&list);

    linked_push(&list, 14);
    linked_push(&list, 17);
    linked_push_tail(&list, 20);
    linked_push_tail(&list, 90);

    linked_display(list);
    return 0;
}

2. 使用哑节点（头节点）模式 #

如果需要避免每次push时判断空链表，可以创建一个不存储有效数据的哑节点，链表的有效节点从哑节点的next开始。这种方式下，push操作不需要处理空链表的特殊情况，直接插入新节点即可：

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

struct ListNode
{
    int val;
    struct ListNode *next;
};

// 初始化带哑节点的链表
void linked_init(struct ListNode **p)
{
    *p = malloc(sizeof(struct ListNode));
    (*p)->next = NULL; // 哑节点的val可以不用初始化
}

// 头插式push（插入到哑节点之后）
void linked_push(struct ListNode **p, int curval)
{
    struct ListNode *temp = malloc(sizeof(struct ListNode));
    temp->val = curval;
    temp->next = (*p)->next;
    (*p)->next = temp;
}

// 尾插式push
void linked_push_tail(struct ListNode **p, int curval)
{
    struct ListNode *new_node = malloc(sizeof(struct ListNode));
    new_node->val = curval;
    new_node->next = NULL;

    struct ListNode *temp = *p;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = new_node;
}

void linked_display(struct ListNode *p)
{
    struct ListNode *temp = p->next; // 跳过哑节点
    while (temp)
    {
        printf("%d\n", temp->val);
        temp = temp->next;
    }
}

int main()
{
    struct ListNode *list;
    linked_init(&list);

    linked_push(&list, 14);
    linked_push(&list, 17);
    linked_push_tail(&list, 20);
    linked_push_tail(&list, 90);

    linked_display(list);
    return 0;
}

3. 扩展节点结构体添加状态标记 #

如果一定要保留预分配尾节点的逻辑，可以给节点结构体增加一个bool is_valid标记，明确表示该节点是否存储有效数据，避免用特殊值判断的冲突问题：

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

struct ListNode
{
    int val;
    bool is_valid; // 标记节点是否存储有效数据
    struct ListNode *next;
};

void linked_init(struct ListNode **p)
{
    *p = malloc(sizeof(struct ListNode));
    (*p)->next = NULL;
    (*p)->is_valid = false; // 初始化为未使用状态
}

void linked_push(struct ListNode **p, int curval)
{
    struct ListNode *temp = *p;
    // 找到未使用的尾节点
    while (temp->next != NULL)
    {
        temp = temp->next;
    }

    if (!temp->is_valid)
    {
        temp->val = curval;
        temp->is_valid = true;
    }
    else
    {
        // 创建新节点并标记为有效
        struct ListNode *new_node = malloc(sizeof(struct ListNode));
        new_node->val = curval;
        new_node->is_valid = true;
        new_node->next = NULL;
        temp->next = new_node;
    }
}

void linked_display(struct ListNode *p)
{
    struct ListNode *temp = p;
    while (temp)
    {
        if (temp->is_valid)
        {
            printf("%d\n", temp->val);
        }
        temp = temp->next;
    }
}

int main()
{
    struct ListNode *list;
    linked_init(&list);

    linked_push(&list, 14);
    linked_push(&list, 17);
    linked_push(&list, 20);
    linked_push(&list, 90);

    linked_display(list);
    return 0;
}

内容的提问来源于stack exchange，提问作者Sai Surisetti