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

题目

链表节点：头插法建立单链表并遍历

思路

本题用单链表存整数：头插法建表，再从头到尾遍历打印。

节点含 int v 和 next 指针；每读一个值 new->next=head; head=new。遍历：while(head){ 输出; head=head->next; }，注意释放内存（若题目要求）。

解题分析

头插法：新节点 next 指向原 head，head 更新。读入顺序与输出顺序相反。若要保序可尾插，维护 tail 指针。

完整程序

#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;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        struct Node *p = malloc(sizeof *p);
        p->v = x;
        p->next = head;
        head = p;
    }
    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