PTA（链表）1-5 头插法创建单链表（C）

1-5 头插法创建单链表（C）

分数 7

作者 李廷元

单位 中国民用航空飞行学院

本题要求实现两个函数，输入n个数据，采用头插法创建单链表并打印。例如：如果输入4
，再输入3 7 9 5，则应打印输出5 9 7 3。

链表结点结构定义：

1
2
3
4
struct Node {    //链表结点
    int data;    //数据
    struct Node* link;    //指向下一个结点的指针
};

函数接口定义：

1
2
3
/* 头插法建立单链表：返回单链表的头指针 */
struct Node* buildLinkedList(int* arr, int n);    /* 头插法建立单链表 */
void printLinkedList(struct Node* head);          /* 打印链表 */

其中arr和n是用户传入的参数，n的值不超过100000。head为单链表的头指针。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <stdlib.h>//malloc函数

struct Node {    //链表结点
    int data;    //数据
    struct Node* link;    //指向下一个结点的指针
};

/* 头插法建立单链表：返回单链表的头指针 */
struct Node* buildLinkedList(int* arr, int n);    /* 头插法建立单链表 */
void printLinkedList(struct Node* head);          /* 打印链表 */

int main(int argc, char const *argv[]) {
    int n, i;
    int* a;
    scanf("%d", &n);
    a = (int*)malloc(n * sizeof(int));    //动态内存分配申请数组空间
    for (i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }

    struct Node* head = NULL;    //声明一个指针变量head

    //创建链表，把返回的头指针赋值给head指针变量
    head = buildLinkedList(a, n);

    //打印链表：整个链表用head来代表。
    printLinkedList(head);

    free(a);    //释放存储空间

    return 0;
}

/* 请在这里填写答案 */

输入样例：

输入包含两行。
第一行为数据个数n，不超过100000。
第二行为n个空格分隔的整数，其值不超过int值的范围。

1
2
4
3 7 9 5

输出样例：

在一行输出链表每个结点中的数据，以空格分隔，但行尾无多余空格。

1
5 9 7 3

带头结点答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct Node* buildLinkedList(int* arr, int n) {
    // 指向一个头结点
    struct Node *head = (struct Node*) malloc(sizeof(struct Node));
    head->link = NULL;
    int i = 0;
    while (i < n) {
        struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
        newNode->data = arr[i];
        newNode->link = head->link;
        head->link = newNode;
        i++;
    }
    return head;
}

void printLinkedList(struct Node* head) {
    struct Node* p = head->link; // 用于遍历链表
    int isFront = 1;
    while (p != NULL) {
        if (!isFront) {
            printf(" ");
        }

        printf("%d", p->data);
        isFront = 0;

        p = p->link;
    }
}

不带头结点答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct Node* buildLinkedList(int* arr, int n) {
    struct Node* head = NULL; // 初始时链表为空，头指针为NULL
    int i;
    for (i = 0; i < n; i++) {
        // 1. 创建新结点
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = arr[i];

        // 2. 将新结点插入到当前链表的头部（头插法）
        newNode->link = head; // 新结点的指针指向原来的第一个结点（即head）
        head = newNode;       // head指针指向新结点，新结点成为新的第一个结点
    }
    return head;
}
void printLinkedList(struct Node* head) {
    struct Node* p = head; // 用于遍历链表
    int isFront = 1;
    while (p != NULL) {
        if (!isFront) {
            printf(" ");
        }
        printf("%d", p->data);
        isFront = 0;
        
        p = p->link;
    }
}