PTA-学校-数据结构（求链式线性表的倒数第K项、两个有序链表序列的合并、两个有序链表序列的交集）

2-2 求链式线性表的倒数第K项

分数 5

作者 DS课程组

单位 浙江大学

给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。

输入格式:

输入首先给出一个正整数K，随后是若干非负整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。

输出格式:

输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息NULL。

输入样例:

4 1 2 3 4 5 6 7 8 9 0 -1

输出样例:

7

解析

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode,* LinkList;
int main() {
    int n;
    scanf ("%d", &n);
    if (n <= 0) {
        printf ("NULL");
        return 0;
    }
    LNode* head = (LNode*)malloc(sizeof(LNode));
    head->next = NULL;
    LinkList tail = head;
    int cou = 0;
    while (1) {
        LNode* p = (LNode*)malloc(sizeof(LNode));
        int num;
        scanf ("%d", &num);
        if (num < 0) {
            break;
        }
        p->next = NULL;
        p->data = num;
        tail->next = p;
        tail = p;
        cou++;
    }
    LinkList prev = head->next;
    LinkList curr = head->next;
    if (cou < n ) {
        printf ("NULL");
    }
    else {
        int i = 0;
        for (i = 0; i < n; i++) {
            prev = prev->next;
        }
        while (prev != NULL) {
            prev = prev->next;
            curr = curr->next;
        }
        printf("%d", curr->data);
    }
    LinkList current = head; // 从 head 开始
    while (current != NULL) {
        LinkList temp = current; // 保存当前节点
        current = current->next; // 移动到下一个节点
        free(temp); // 释放当前节点（包括 head 和所有数据节点）
    }
    return 0;
}

注意

题目说的是碰到负数就停止，不是碰到-1

2-3 两个有序链表序列的合并

分数 4

作者 DS课程组

单位 浙江大学

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 3 5 -1
2 4 6 8 10 -1

输出样例:

1 2 3 4 5 6 8 10

解析

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode,* LinkList;
int main() {
    LinkList L1 = (LNode*)malloc(sizeof(LNode));
    LinkList L2 = (LNode*)malloc(sizeof(LNode));
    L1->next = NULL;
    L2->next = NULL;
    LinkList tail1 = L1;
    LinkList tail2 = L2;
    while (1) {
        int num;
        scanf("%d", &num);
        if (num < 0) {
            break;;
        }
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = num;
        p->next = NULL;
        tail1->next = p;
        tail1 = p;
    }
    while (1) {
        int num;
        scanf("%d", &num);
        if (num < 0) {
            break;;
        }
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = num;
        p->next = NULL;
        tail2->next = p;
        tail2 = p;
    }
    LinkList L3 = (LNode*)malloc(sizeof(LNode));
    LinkList tail3 = L3;
    LinkList head1 = L1->next;
    LinkList head2 = L2->next;
    if (head1 == NULL && head2 ==NULL) {
        printf ("NULL");
        return 0;
    }
    while (head1 != NULL && head2 != NULL) {
        if (head1->data < head2->data) {
            LinkList p = (LNode*)malloc(sizeof(LNode));
            p->data = head1->data;
            p->next = NULL;
            tail3->next = p;
            tail3 = p;
            head1 = head1->next;
        }
        else {
            LinkList p = (LNode*)malloc(sizeof(LNode));
            p->data = head2->data;
            p->next = NULL;
            tail3->next = p;
            tail3 = p;
            head2 = head2->next;
        }
    }
    if (head1 != NULL) {
        tail3->next = head1;
    }
    else {
        tail3->next = head2;
    }
    LinkList head3 = L3->next;
    int flag = 1;
    while (head3 != NULL) {
        if (flag == 1) {
            printf ("%d", head3->data);
            flag = 0;
        }
        else {
            printf (" %d", head3->data);
        }
        head3 = head3->next;
    }
    return 0;
}

2-4 两个有序链表序列的交集

分数 6

作者 DS课程组

单位 浙江大学

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 2 5 -1
2 4 5 8 10 -1

输出样例:

2 5

作者的代码

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode,*LinkList;
int main() {
    LinkList L1 = (LNode*)malloc(sizeof(LNode));
    LinkList L2 = (LNode*)malloc(sizeof(LNode));
    L1->next = NULL;
    L2->next = NULL;
    LinkList tail1 = L1;
    LinkList tail2 = L2;
    int count1 = 0;
    int count2 = 0;
    while (1) {
        int num;
        scanf("%d", &num);
        if (num < 0) {
            break;;
        }
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = num;
        p->next = NULL;
        tail1->next = p;
        tail1 = p;
        count1++;
    }
    while (1) {
        int num;
        scanf("%d", &num);
        if (num < 0) {
            break;;
        }
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = num;
        p->next = NULL;
        tail2->next = p;
        tail2 = p;
        count2++;
    }
    LinkList L3 = (LNode*)malloc(sizeof(LNode));
    LinkList tail = L3;
    if (count1 < count2) {
        LinkList p1 = L1->next;
        LinkList p2 = L2->next;
        int i;
        for (i = 0; i < count1; i++) {
            while (p2 != NULL) {
                if (p1->data == p2->data) {
                    LinkList curr = (LNode*)malloc(sizeof(LNode));
                    curr->next = NULL;
                    curr->data = p2->data;
                    tail->next = curr;
                    tail = curr;
                }
                p2 = p2->next;
            }
            p2 = L2->next;
            p1 = p1->next;
        }
    }
    else {
        LinkList p1 = L1->next;
        LinkList p2 = L2->next;
        int i;
        for (i = 0; i < count1; i++) {
            while (p1 != NULL) {
                if (p2->data == p1->data) {
                    LinkList curr = (LNode*)malloc(sizeof(LNode));
                    curr->next = NULL;
                    curr->data = p1->data;
                    tail->next = curr;
                    tail = curr;
                }
                p1 = p1->next;
            }
            p1 = L1->next;
            p2 = p2->next;
        }
    }
    tail = L3->next;
    if (tail == NULL) {
        printf("NULL");
        return 0;
    }
    int flag = 1;
    while (tail != NULL) {
        if (flag == 1) {
            printf("%d", tail->data);
            flag = 0;
        }
        else {
            printf(" %d", tail->data);
        }
        tail = tail->next;
    }
    return 0;
}

超时了

解析

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

// 定义链表节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

int main() {
    Node *list1 = NULL, *list2 = NULL;
    Node *tail1 = NULL, *tail2 = NULL;
    int num;
    
    // 读取第一个链表
    while (scanf("%d", &num) == 1 && num != -1) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = num;
        newNode->next = NULL;
        
        if (list1 == NULL) {
            list1 = newNode;
            tail1 = newNode;
        } else {
            tail1->next = newNode;
            tail1 = newNode;
        }
    }
    
    // 读取第二个链表
    while (scanf("%d", &num) == 1 && num != -1) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = num;
        newNode->next = NULL;
        
        if (list2 == NULL) {
            list2 = newNode;
            tail2 = newNode;
        } else {
            tail2->next = newNode;
            tail2 = newNode;
        }
    }
    
    // 求交集并直接输出，不构建新链表
    Node *p1 = list1, *p2 = list2;
    int first = 1; // 标记是否是第一个输出
    int found = 0; // 标记是否找到交集元素
    
    while (p1 != NULL && p2 != NULL) {
        if (p1->data == p2->data) {
            if (!first) {
                printf(" ");
            }
            printf("%d", p1->data);
            first = 0;
            found = 1;
            
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->data < p2->data) {
            p1 = p1->next;
        } else {
            p2 = p2->next;
        }
    }
    
    if (!found) {
        printf("NULL");
    }
    printf("\n");
    
    // 释放内存
    while (list1 != NULL) {
        Node* temp = list1;
        list1 = list1->next;
        free(temp);
    }
    
    while (list2 != NULL) {
        Node* temp = list2;
        list2 = list2->next;
        free(temp);
    }
    
    return 0;
}

优化说明：

1. 减少函数调用：
   • 移除了所有辅助函数，直接在 main 函数中操作，减少函数调用开销
2. 优化链表构建：
   • 使用尾指针直接构建链表，避免每次都要遍历到链表末尾
3. 边求交集边输出：
   • 不构建结果链表，直接在求交集过程中输出结果，减少内存分配和释放
4. 简化逻辑：
   • 使用更直接的指针操作，避免不必要的复杂逻辑
5. 输入处理优化：
   • 直接使用 scanf 读取输入，检查返回值确保正确读取

这个版本应该能够处理大数据量的输入而不会超时。如果仍然超时，可能需要考虑其他因素，比如输入数据量特别大或者评测系统的限制。