编程题 02-线性结构3 Reversing Linked List【PAT】

绯樱殇雪

已于 2025-05-12 16:40:18 修改

阅读量446

点赞数 15

分类专栏： PTA 文章标签： c++ pat考试

于 2025-05-12 16:30:06 首次发布

本文链接：https://blog.csdn.net/qq_41918107/article/details/147899090

版权

PTA 专栏收录该内容

65 篇文章

订阅专栏

文章目录

题目
题解
- 解题思路
- 完整代码

编程练习题目集目录

题目

Given a constant $K$ and a singly linked list $L$ , you are supposed to reverse the links of every $K$ elements on $L$ . For example, given L being $1 \to 2 \to 3 \to 4 \to 5 \to 6$ , if $K = 3$ , then you must output $3 \to 2 \to 1 \to 6 \to 5 \to 4$ ; if $K = 4$ , you must output $4 \to 3 \to 2 \to 1 \to 5 \to 6$ .

输入格式

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive $N（≤10^5）$ which is the total number of nodes, and a positive $K （ \leq N ）$ which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by $- 1$ .

Then $N$ lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

输出格式

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

输入样例

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

题解

解题思路

使用两个数组 $d a t a$ 和 $n e x t$ 分别存储每个节点的数据和指向下一个节点的指针。从头节点开始，按顺序将节点的地址存储在数组 $l i s t$ 中，构建链表的顺序结构。将 $l i s t$ 中的节点按分组大小 $K$ 进行反转。将反转后的节点顺序存储在结果数组 $res u lt$ 中，即可。

完整代码

#include <iostream>
using namespace std;

int main(void) {
    int number, k, n, sum = 0;
    cin >> number >> n >> k;
    int temp, data[100005], next[1000005], list[100005], result[100005];

    // 读取链表节点信息
    for (int i = 0; i < n; i++) {
        cin >> temp;
        cin >> data[temp] >> next[temp];
    }

    // 构建初始链表顺序
    while (number != -1) {
        list[sum++] = number;
        number = next[number];
    }

    // 复制初始链表到结果数组
    for (int i = 0; i < sum; i++) result[i] = list[i];

    // 按照分组大小 K 反转链表中的每个分组
    for (int i = 0; i < (sum - sum % k); i++)
        result[i] = list[i / k * k + k - 1 - i % k];

    // 输出反转后的链表
    for (int i = 0; i < sum - 1; i++)
        printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]);
    printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);

    return 0;
}