题目链接

https://pintia.cn/problem-sets/994805260223102976/problems/994805296180871168

题解

第一遍没有全部AC，最后1个测试点没过，原因是题目给的结点中有可能有无效结点，所以需要重新统计节点个数。（参考链接：https://blog.csdn.net/m0_37285185/article/details/68936043）

修改后全部都AC了。

整体的思路是以地址为键形成一个map，根据从第一个结点开始遍历，统计出有效结点的地址顺序（存储在数组中），最后利用reverse函数将顺序反转，最后将反转的链表输出。

// PAT BasicLevel 1025

// https://pintia.cn/problem-sets/994805260223102976/problems/994805296180871168

#include <iostream>

#include <map>

#include <algorithm>

using namespace std;

class Node{

public:

    int address;

    int data;

    int next;

    // 因为使用map，所以需要提供一个无参构造

    Node(){};

    Node(int address,int data,int next){

        this->address = address;

        this->data = data;

        this->next = next;

    }

    void print(){

        printf("%05d", address);

        cout  << ' ' << data << ' ';

        if(next==-1){

            printf("%d\n",next);

        }else{

            printf("%05d\n", next);

        }

    }

};

int main()

{

    // 获取n、k和首结点地址

    int n, k, head;

    cin >> head >> n >> k;

    // 利用map模拟链表，获取用户输入的结点

    int address,data,next;

    map<int,Node> nodes;

    for(int i=0;i<n;++i){

        cin >> address >> data >> next;

        nodes[address]=Node(address,data,next);

    }

    // 获取结点地址的顺序并重新统计结点个数去除无效顶点

    int * addressArr=new int[n];

    addressArr[0] = head;

    address = nodes[head].next;

    int nodeCount=1;

    while(address!=-1){

        addressArr[nodeCount]=address;

        nodeCount++;

        address = nodes[address].next;

    }

    n=nodeCount;

    // 将结点地址的顺序进行反转

    if (k > 1){

        int *p = addressArr;

        while ((addressArr + n) - p >= k)

        {

            reverse(p, p + k);

            p += k;

        }

    }

    // 更新各结点的next

    for(int i=0;i<n-1;++i){

        nodes[addressArr[i]].next=addressArr[i+1];

    }

    nodes[addressArr[n - 1]].next=-1;

    // 输出反转后的链表

    for (int i = 0; i < n; ++i){

        nodes[addressArr[i]].print();

    }

    // 释放内存

    delete[] addressArr;

    //system("pause");

    return 0;

}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!

巴特西

PAT乙级1025

题目链接

题解

最新文章

热门文章