PTA-学校-数据结构（头插法创建单链表、两个有序链表序列的合并、删除排序链表中的重复元素、求链表的倒数第m个元素、共享后缀的链表、单链表分段逆转、一元多项式求导）

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

分数 7

作者 李廷元

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

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

链表结点结构定义：

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

函数接口定义：

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

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

裁判测试程序样例：

#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值的范围。

4
3 7 9 5

输出样例：

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

5 9 7 3

解析

struct Node* buildLinkedList(int* arr, int n) {
    int i;
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->link = NULL;
    for (i = 0; i < n; i++) {
        struct Node* L = (struct Node*)malloc(sizeof(struct Node));
        L->link = head->link;
        L->data = arr[i];
        head->link = L;
    }
    return head;
}

void printLinkedList(struct Node* head) {
    int flag = 1;
    struct Node* curr = (struct Node*)malloc(sizeof(struct Node));
    curr = head->link;
    while (curr != NULL) {
        if (flag == 1) {
            printf ("%d",curr->data);
            flag = 0;
        }
        else {
            printf (" %d",curr->data);
        }
        curr = curr->link;
    }
}

注意

1.打印是先“%d”，然后“ %d”。因为如果链表只由一个元素，先打印%d不会有空格。

1-6 两个有序链表序列的合并

分数 5

作者 DS课程组

单位 浙江大学

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义：

List Merge( List L1, List L2 );

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。

裁判测试程序样例：

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

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

3
1 3 5
5
2 4 6 8 10

输出样例：

1 2 3 4 5 6 8 10 
NULL
NULL

作者第一次代码

List Merge( List L1, List L2 ) {
    PtrToNode p1;
    PtrToNode p2;
    p1 = L1->Next;
    p2 = L2->Next;
    struct Node * head = (struct Node *)malloc(sizeof(struct Node));
    head->Next = NULL;
    struct Node * curr = (struct Node *)malloc(sizeof(struct Node));
    curr->Next = head;
    while (p1 != NULL && p2 != NULL) {
        if (p1->Data < p2->Data) {
            struct Node * cu = (struct Node *)malloc(sizeof(struct Node));
            cu->Data = p1->Data;
            cu->Next = curr->Next;
            curr->Next = cu;
            p1 = p1->Next;
            curr= curr->Next;
        }
        else {
            struct Node * cu = (struct Node *)malloc(sizeof(struct Node));
            cu->Data = p2->Data;
            cu->Next = curr->Next;
            curr->Next = cu;
            p2 = p2->Next;
            curr= curr->Next;
        }
    }
    if (p1 == NULL) {
        curr->Next = p2;
    }
    else {
        curr->Next = p1;
    }
    p1->Next = NULL;
    p2->Next = NULL;
}

1. 函数无返回值（最直接原因）

Merge 函数的返回类型是 List（链表头指针），但你的代码末尾没有 return 语句。这会导致主函数 main 调用 Merge 时，拿到的是随机无效指针，后续 Print(L) 访问该无效指针时，直接触发段错误。

2. 空指针访问（循环结束后）

循环结束后，你直接执行 p1->Next = NULL 和 p2->Next = NULL，但此时 p1 或 p2 可能已经是 NULL（例如，若 L1 的节点先遍历完，p1 会是 NULL）。访问 NULL->Next 属于典型的空指针访问，会立即触发段错误。

3. 错误创建新节点（违反题目要求）

题目明确要求 “直接使用原序列中的结点”，但你的代码每次都通过 malloc 新建 cu 节点并复制数据，这不仅不符合题意，还会导致原链表节点被废弃，同时增加内存泄漏风险（新建的 cu 未释放）。

4. 遍历指针 curr 初始化错误

你通过 malloc 新建 curr 节点，并设置 curr->Next = head，这会额外创建一个无用节点，导致链表结构混乱。正确的做法是让 curr 直接指向 head（作为合并链表的 “尾指针”，跟踪最后一个节点），无需新建。

解析

List Merge( List L1, List L2 ) {
    PtrToNode p1;
    PtrToNode p2;
    p1 = L1->Next;
    p2 = L2->Next;
    struct Node * head = (struct Node *)malloc(sizeof(struct Node));
    head->Next = NULL;
    struct Node * curr = (struct Node *)malloc(sizeof(struct Node));
    curr = head;
    while (p1 != NULL && p2 != NULL) {
        if (p1->Data < p2->Data) {
            curr->Next = p1;
            p1 = p1->Next;
        }
        else {
            struct Node * cu = (struct Node *)malloc(sizeof(struct Node));
            curr->Next = p2;
            p2 = p2->Next;
        }
        curr = curr->Next;
    }
    if (p1 == NULL) {
        curr->Next = p2;
    }
    else {
        curr->Next = p1;
    }
    L1->Next = NULL;
    L2->Next = NULL;
    return head;
}

注意

curr类似于尾指针

1-7 删除排序链表中的重复元素

分数 7

作者 李廷元

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

题目描述：删除排序链表中的重复元素

编写一个函数，对于一个给定的排序链表，删除所有重复的元素每个元素只留下一个。

给出1->1->2->NULL，返回 1->2->NULL

给出1->1->2->3->3->NULL，返回 1->2->3->NULL

单链表结点类型定义：

typedef int ElemType;    //元素的数据类型

typedef struct LNode {
    ElemType data;        //结点的数据域
    struct LNode *next;    //指向后继结点
} LinkNode;             //单链表结点类型

函数接口定义：

/*尾插法建立单链表,细节不表*/
LinkNode* CreateListR(ElemType a[], int n);

/*输出线性表,细节不表*/
void DispList(LinkNode *L);

/*删除排序链表中的重复元素*/
LinkNode* deleteDuplicates(LinkNode *L);

其中 L是单链表的头指针。 数组a[] 存放创建无序单链表的元素，n为数组长度，其值不超过10000。

裁判测试程序样例：

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

typedef int ElemType;    /*元素的数据类型*/

typedef struct LNode {    /*单链表结点类型定义*/
    ElemType data;        /*结点的数据域*/
    struct LNode *next;    /*指向后继结点*/
} LinkNode;             /*单链表结点类型*/

/*尾插法建立单链表,细节不表*/
LinkNode* CreateListR(ElemType a[], int n);

/*输出线性表,细节不表*/
void DispList(LinkNode *L);

/*删除排序链表中的重复元素*/
LinkNode* deleteDuplicates(LinkNode *L);

int main()
{    
    ElemType a[10000], x;
    int n = 0;

    while (scanf("%d", &x) != EOF) {
        a[n++] = x;
    }

    LinkNode* L = CreateListR(a, n);

    L = deleteDuplicates(L);
    DispList(L);

    return 0;
}

/* 请在下面填写答案 */

输入样例：

输入只有1行，在该行给出有序单链表的所有元素。

1 1 2 3 3

输出样例：

输出只有1行，在该行输出删除重复元素后的有序单链表，元素之间以一个空格分隔，行尾无多余的空格。

1 2 3

解析

LinkNode* deleteDuplicates(LinkNode *L) {
    if (L == NULL || L->next == NULL) {
        return L;
    }
    LinkNode *curr = L;
    while (curr->next != NULL) {
        if (curr->data == curr->next->data) {
            LinkNode *temp = curr->next;
            curr->next = temp->next;
            free(temp);
        }
        else{
            curr = curr->next;
        }
    }
    return L;
}

注意

要从第一个开始*LinkNode curr = L；

1-8 求链表的倒数第m个元素

分数 5

作者 DS课程组

单位 浙江大学

请设计时间和空间上都尽可能高效的算法，在不改变链表的前提下，求链式存储的线性表的倒数第m（>0）个元素。

函数接口定义：

ElementType Find( List L, int m );

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L是给定的带头结点的单链表；函数Find要将L的倒数第m个元素返回，并不改变原链表。如果这样的元素不存在，则返回一个错误标志ERROR。

裁判测试程序样例：

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

#define ERROR -1

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表 */

ElementType Find( List L, int m );

int main()
{
    List L;
    int m;
    L = Read();
    scanf("%d", &m);
    printf("%d\n", Find(L,m));
    Print(L);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

5
1 2 4 5 6
3

输出样例：

4
1 2 4 5 6 

作者第一次答案

ElementType Find( List L, int m ) {
    PtrToNode p1 = L;
    int i;
    for (i = 0; i < m; i++) {
        if (p1 == NULL) {
            return -1;
        }
        p1 = p1->Next;
    }
    if (p1 == NULL) {
        return -1;
    }
    PtrToNode p2 = L;
    while (p1 != NULL) {
        p1 = p1->Next;
        p2 = p2->Next;
    }
    return p2->Data;
}

解析

ElementType Find( List L, int m ) {
    PtrToNode p1 = L;
    int i;
    for (i = 0; i < m; i++) {
        if (p1 == NULL) {
            return ERROR;
        }
        p1 = p1->Next;
    }
    PtrToNode p2 = L;
    while (p1 != NULL) {
        p1 = p1->Next;
        p2 = p2->Next;
    }
    return p2->Data;
}

注意

是返回ERROR不是**-1**

1-9 共享后缀的链表

分数 6

作者 陈越

单位 浙江大学

有一种存储英文单词的方法，是把单词的所有字母串在一个单链表上。为了节省一点空间，如果有两个单词有同样的后缀，就让它们共享这个后缀。下图给出了单词“loading”和“being”的存储形式。本题要求你找出两个链表的公共后缀。

函数接口定义：

PtrToNode Suffix( List L1, List L2 );

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L1和L2都是给定的带头结点的单链表。函数Suffix应返回L1和L2的公共后缀的起点位置。

裁判测试程序样例：

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

typedef char ElementType;

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

void ReadInput( List L1, List L2 ); /* 裁判实现，细节不表 */
void PrintSublist( PtrToNode StartP ); /* 裁判实现，细节不表 */
PtrToNode Suffix( List L1, List L2 );

int main()
{
    List L1, L2;
    PtrToNode P;

    L1 = (List)malloc(sizeof(struct Node));
    L2 = (List)malloc(sizeof(struct Node));
    L1->Next = L2->Next = NULL;
    ReadInput( L1, L2 );
    P = Suffix( L1, L2 );
    PrintSublist( P );

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

如图存储的链表

输出样例：

ing

先想到是对地址做比较，但是一次次比较非常耗时，所以先使他们长度等长再对比，那么就需要一个新的函数：求长度函数。所以这道题需要函数套函数

解析

int getlength (List L) {
    PtrToNode p;
    p = L;
    int length = 0;
    while (p != NULL) {
        p = p->Next;
        length++;
    }
    return length;
}
PtrToNode Suffix( List L1, List L2 ) {
    PtrToNode p1 = L1->Next;
    PtrToNode p2 = L2->Next;
    int n1 = getlength(L1);
    int n2 = getlength(L2);
    int n3;
    int flag = 1;
    int i;
    if (n1 > n2) {
        n3 = n1 - n2;
    }
    else {
        flag = -1;
        n3 = n2 - n1;
    }
    if (flag == 1) {
        for (i = 0; i < n3; i++) {
            p1 = p1->Next;
        }
    }
    else {
        for (i = 0; i < n3; i++) {
            p2 = p2->Next;
        }
    }
    while (p1 != NULL && p2 != NULL) {
        if (p1 == p2) {
            return p1;
        }
        p1 = p1->Next;
        p2 = p2->Next;
    }
    return NULL;
}

1-10 单链表分段逆转

分数 6

作者 陈越

单位 浙江大学

给定一个带头结点的单链表和一个整数K，要求你将链表中的每K个结点做一次逆转。例如给定单链表 1→2→3→4→5→6 和 K=3，你需要将链表改造成 3→2→1→6→5→4；如果 K=4，则应该得到 4→3→2→1→5→6。

函数接口定义：

void K_Reverse( List L, int K );

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L是给定的带头结点的单链表，K是每段的长度。函数K_Reverse应将L中的结点按要求分段逆转。

裁判测试程序样例：

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

typedef int ElementType;

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

List ReadInput(); /* 裁判实现，细节不表 */
void PrintList( List L ); /* 裁判实现，细节不表 */
void K_Reverse( List L, int K );

int main()
{
    List L;
    int K;

    L = ReadInput();
    scanf("%d", &K);
    K_Reverse( L, K );
    PrintList( L );

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

6
1 2 3 4 5 6
4

输出样例：

4 3 2 1 5 6

图像解析

解析

void K_Reverse( List L, int K ) {
    if (K <= 1) {
        return;
    }
    PtrToNode p = L;
    while (p->Next != NULL) {
        int n = 0;
        PtrToNode check = p;
        while (check->Next != NULL && n < K) {
            check = check->Next;
            n++;
        }
        if (n < K) {
            return;
        }
        PtrToNode tail = p->Next;  // 当前段的第一个节点，逆转后将变成尾节点
        PtrToNode curr = tail->Next;  // 从第二个节点开始处理

        // 将后续K-1个节点依次插入到当前段头部
        for (int i = 1; i < K; i++) {
            tail->Next = curr->Next;  // 将curr节点从链表中取下
            curr->Next = p->Next;     // 将curr插入到p节点后面
            p->Next = curr;           // 更新p的Next指针
            curr = tail->Next;        // 处理下一个节点
        }
        // 移动p到当前段的尾节点，准备处理下一段
        p = tail;
    }
}

注意

如果分段小于一则不用操作，直接return

如果大于一，先要判断链表是否存在长度为K的，不然无法逆转。使check为头节点，n为计数器，初始值为0。

在K中，见图像解析。先跳过这个元素，再把这个元素重新插入头节点之后。

2-1 一元多项式求导

分数 5

作者 DS课程组

单位 浙江大学

设计函数求一元多项式的导数。

输入格式:

以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
注意：零多项式用 0 0 表示。

输出格式:

以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。

输入样例:

3 4 -5 2 6 1 -2 0

输出样例:

12 3 -10 1 6 0

解析

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
    ElemType coeff; //系数
    ElemType power; //指数
    struct LNode *next;
}LNode,* LinkList;

LNode * creatLNode() {
    LinkList head = (LNode *)malloc(sizeof(LNode));
    head->next = NULL;

    int coeff;
    int power;
    LinkList tail = head;
    while (scanf ("%d %d" , &coeff, &power) == 2) {
        LNode *p = (LNode *)malloc(sizeof(LNode));
        p->coeff = coeff;
        p->power = power;
        p->next = NULL;
        tail->next = p;
        tail = p;
    }
    return head;
}

LNode * daoLNode(LNode * L) {
    LinkList head = (LNode *) malloc(sizeof(LNode));
    head->next = NULL;

    int coeff_curr;
    int power_curr;
    LinkList tail = head;
    LinkList old = L->next;
    while (old != NULL) {
        coeff_curr = old->coeff;
        power_curr = old->power;
        if (power_curr > 0) {
            coeff_curr = coeff_curr * power_curr;
            power_curr -= 1;

            LinkList q = (LNode *)malloc(sizeof(LNode));
            q->coeff = coeff_curr;
            q->power = power_curr;
            q->next = NULL;
            tail->next = q;
            tail = q;
        }
        old = old->next;
    }
    return head;
}

void printLNode (LNode * L) {
    LinkList p = L->next;
    if (p == NULL) {
        printf ("0 0");
        return;
    }
    int flag = 1;
    while (p != NULL) {
        if (flag == 1) {
            printf ("%d %d" , p->coeff, p->power);
            flag = 0;
        }
        else {
            printf (" %d %d" , p->coeff, p->power);
        }
        p = p->next;
    }
}

int main() {
    LinkList L1 = creatLNode();
    LinkList L2 = daoLNode(L1);
    printLNode(L2);
    free(L1);
    free(L2);
    return 0;
}