PAT-2019年冬季考试-甲级 7-2 Block Reversing (25分) (链表转置)

7-2 Block Reversing (25分)

Given a singly linked list L. Let us consider every K nodes as a block (if there are less than K nodes at the end of the list, the rest of the nodes are still considered as a block). Your job is to reverse all the blocks in L. For example, given L as 1→2→3→4→5→6→7→8 and K as 3, your output must be 7→8→4→5→6→1→2→3.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤) which is the total number of nodes, and a positive K (≤) which is the size of a block. The address of a node is a 5-digit nonnegative integer, and NULL is represented by −.

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.

Output Specification:

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.

Sample Input:

00100 8 3

71120 7 88666

00000 4 99999

00100 1 12309

68237 6 71120

33218 3 00000

99999 5 68237

88666 8 -1

12309 2 33218

Sample Output:

71120 7 88666

88666 8 00000

00000 4 99999

99999 5 68237

68237 6 00100

00100 1 12309

12309 2 33218

33218 3 -1

题意：

链表的转置。给定N和K，每K个转一转，最后还要整个再转一转。

题解：

这道题挺熟悉的，和1074 Reversing Linked List (25分)差不多嘛。

当时依稀记得，用vector超方便，但是忘了怎么用

reverse(valid.begin()+i*k,valid.begin()+i*k+k);

然后就十分痛苦地用不了现成的reverse，只好把开两个vector当成数组用，然后非常艰难地写完了。。。。

AC代码：

#include<bits/stdc++.h>

using namespace std;

struct node{

    int d;

    int id;

    int nx;

}a[],b[];

vector<node>v;

int main(){

    int n,k;

    int root;

    cin>>root>>n>>k;

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

        int x,y,z;

        cin>>x>>z>>y;

        a[x].d=z;

        a[x].nx=y;

        a[x].id=x;

    }

    node nroot=a[root];

    v.push_back(nroot);

    int num=;

    while(nroot.nx!=-){//先按照链表的顺序存好放到vector中

        nroot=a[nroot.nx];

        v.push_back(nroot);

        num++;

    }

    int cs=num/k;//cs表示要转几次

    for(int i=;i<cs;i++){

        for(int j=;j<k;j++){

            a[i*k+j]=v.at(i*k+k-j-);//每k个转一转，本来可以 reverse(v.begin()+i*k,v()+i*k+k);唉。。。

        }

    }

    int pp=cs*k-;

    if(cs*k<num){//剩下的不到K个也要转

        for(int i=v.size()-;i>=cs*k;i--) a[++pp]=v.at(i);

    }

    for(int i=;i<num;i++){//再整个链表转一下，本来可以reverse(v.begin(),v.end())的,唉。。。

        b[i]=a[num-i-];

    }

    for(int i=;i<num;i++){//修改b数组里每个结构体的nx值

        if(i!=num-) b[i].nx=b[i+].id;

        else b[i].nx=-;

    }

    for(int i=;i<num-;i++){//输出

        printf("%05d %d %05d\n",b[i].id,b[i].d,b[i].nx);

    }

    printf("%05d %d -1",b[num-].id,b[num-].d);

    return ;

}

巴特西

PAT-2019年冬季考试-甲级 7-2 Block Reversing (25分) (链表转置)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

最新文章

热门文章