当前位置：首页 > news >正文

PAT 1025 反转链表

news 来源：原创 2024/5/16 11:41:19

题目

/*
 1025. 反转链表 (25)
 
 给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。
 
 输入格式：
 
 每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 10^5)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。
 
 接下来有N行，每行格式为：
 
 Address Data Next
 
 其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。
 
 输出格式：
 
 对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
 
 输入样例：
 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
 */

思路

// 关键信息
/*
 input：
 地址A 结点数N 间隔K
 地址 内容 next
 
 限制：
 地址A：5位数
 结点数N：<= 10^5
 
 */

// 思路：构建链表，放入顺序表，通过变换顺序表得到所需的序列
// 将单链表每隔 K 个反转，最后不足数的不反转

代码

#include <cstdio>
#include <vector>
#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;

struct Node{
    int addr;
    int a;
    int next;
};

int main(){
    
//  读入
    
    // 第一行
    int root;
    int n;
    int k;
    cin >> root >> n >> k;
    
    // 其余行
    vector<Node> inLst;
    int posOf[100005];
    int cnt = 0;
    
    inLst.clear();
    memset(posOf, -1, sizeof(posOf));
    for (int i = 0; i < n; ++i) {
        Node node;
        cin >> node.addr >> node.a >> node.next;
        
        inLst.push_back(node);
        posOf[node.addr] = cnt++;
    }
    
//  遍历
    vector<Node> linkLst;
    linkLst.clear();
    
    int p = root;
    int i;
    for (i = 0; i < n; ++i) {
        Node node = inLst[posOf[p]];
        linkLst.push_back(node);
        
        p = node.next;
        
        if (p == -1) {
            break;
        }
    }
    
//  变换
    int time = (int)linkLst.size() / k;
    for (int i = 0; i < time; ++i) {
        reverse(linkLst.begin() + i * k, linkLst.begin() + (i + 1) * k);
    }
//  输出
    int size = (int)linkLst.size();
    for (int i = 0; i < size; ++i){
        if (i == size - 1) {
            printf("%05d %d -1\n",linkLst[i].addr,linkLst[i].a);
        }else{
            printf("%05d %d %05d\n",linkLst[i].addr,linkLst[i].a,linkLst[i+1].addr);
        }
    }
    return 0;
}

过程资料

编码列表
1、三个测试点没过： http://paste.ubuntu.com/9844549/
2、过多的边界情况：逻辑上问题，设计得过于复杂，处理子串K的时候与前后杂糅在一起，导致一系列错误：http://paste.ubuntu.com/9847027/
3、AC，通过多个临时变量减轻子串K与前后的杂糅，依旧不推荐这种，过于复杂易错：http://paste.ubuntu.com/9847572/
4、AC，离散化方法寻址，再将链表结点按序存储为顺序表，十分方便：http://paste.ubuntu.com/9849986/

注意点：