C 语言第79题：链表节点：头插法建立单链表并遍历

题目

定义单链表节点结构体，使用头插法（Head Insertion）依次读入 n 个整数建立单向链表，并顺序遍历输出链表中各节点的值。

输入格式：第一行输入节点数量 n；第二行输入 n 个整数。

输出格式：按链表当前从头到尾的顺序输出各节点数据，末尾换行。

数据范围与约定：1 ≤ n ≤ 100。

思路与算法

1. 链表节点内存动态分配
为每个新节点调用 malloc(sizeof(struct Node)) 申请堆内存。

2. 头插法指针重连
核心操作：node->next = head; head = node;。新节点始终插入在表头位置，因此最终遍历出来的顺序恰好是输入的逆序。

3. 内存释放习惯
程序结束前应顺着指针释放每个动态分配的节点，养成防止内存泄漏的规范。

完整程序

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

// 单链表节点定义
struct Node {
    int v;
    struct Node *next;
};

int main(void)
{
    int n, x;
    struct Node *head = NULL;
    if (scanf("%d", &n) != 1 || n < 1) {
        return 1;
    }

    // 头插法建表：新节点的 next 指向当前 head，随后 head 更新为新节点
    // 特点：后续遍历出来的顺序与输入顺序相反（逆序）
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        struct Node *p = malloc(sizeof *p);
        p->v = x;
        p->next = head;
        head = p;
    }

    // 遍历链表直到遇到 NULL
    for (struct Node *p = head; p; p = p->next) {
        printf("%d ", p->v);
    }
    putchar('\n');
    return 0;
}

运行示例

输入：

3
1 2 3

输出：

3 2 1

其它写法

下面每种写法都是完整程序，输入输出格式与正文一致，便于对照。

尾插法保序

程序：

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

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

int main(void)
{
    int n, x;
    struct Node *head = NULL, *tail = NULL;
    if (scanf("%d", &n) != 1 || n < 1) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        struct Node *p = malloc(sizeof *p);
        p->v = x;
        p->next = NULL;
        if (!head) {
            head = tail = p;
        } else {
            tail->next = p;
            tail = p;
        }
    }
    for (struct Node *p = head; p; p = p->next) {
        printf("%d ", p->v);
    }
    putchar('\n');
    return 0;
}

输入：

3
1 2 3

输出：

1 2 3