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 (≤105) which is the total number of nodes, and a positive K (≤N) which is the size of a block. 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.

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

题意：

给定一个单链链表L，让我们把每个K个节点看作一个块（如果列表末尾的节点少于K个，那么其余的节点仍然被看作一个块）。你的工作是反转L中的所有块。例如，给定L为1→2→3→4→5→6→7→8和K为3，你的输出必须是7→8→4→5→6→1→2→3。

输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行包含第一节点的地址、节点总数的正N（≤105）和块大小的正K（≤N）。节点的地址是一个5位非负整数，空值由-1表示。

接下来是N行，每行描述一个节点的格式为

Address Data Next

其中Address是节点的位置，Data是整数，Next是下一个节点的位置。
输出规格：
对于每种情况，输出结果的有序链表。每个节点占用一行，并以与输入相同的格式打印。

代码：

1.　解法一（来源于网络）
使用sort的方法巧妙将链表反转：三阶排序：1.is0k 2.group 3.index
对于这道题来说，主要是group比较重要，在Node的结构里直接加入{group、index}，初始化后进行排序！

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct Node { 
    int data,address,next;
    int isOk;
    int group, index;
    Node (){ 
        isOk=0;
    }
}node[100010];
bool cmp(Node a, Node b){ 
    if (a.isOk!=b.isOk) return a.isOk>b.isOk;
    else if (a.group!=b.group) return a.group>b.group;
    else return a.index<b.index;
}
int main(){ 
    int n,k;
    int begin;
    scanf("%d %d %d",&begin, &n, &k);
    for (int i=0; i<n; i++){ 
        int address, data, next;
        scanf("%d %d %d",&address, &data, &next);
        node[address].data=data;
        node[address].address=address;
        node[address].next=next;
    }
    int p=begin;
    int cnt=0;
    //group a[group][index]
    while (p!=-1){ 
        node[p].group=cnt/k;
        node[p].index=cnt%k;
        cnt++;
        node[p].isOk=1;
        p=node[p].next;
    }
    sort(node, node+100010, cmp);
    for (int i=0; i<cnt; i++){ 
        if (i!=cnt-1){ 
            printf("%05d %d %05d\n",node[i].address, node[i].data, node[i+1].address);
        }else { 
            printf("%05d %d -1\n",node[i].address, node[i].data);
        }
    }
    return 0;
}

2.　解法二（来源于网络）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
struct Node
{ 
    int data, nex;
}node[maxn];
void Print(const vector<int> & ans)
{ 
    if(ans.size() == 0)
    { 
        printf("0 -1");
    }else
    { 
        for(int i = 0; i < ans.size(); ++i)
        { 
            if(i < ans.size() - 1) printf("%05d %d %05d\n", ans[i], node[ans[i]].data, ans[i+1]);
            else printf("%05d %d -1\n", ans[i], node[ans[i]].data);
        }
    }
}
int main()
{ 
    int first, n, k;
    scanf("%d %d %d", &first, &n, &k);
    for(int i = 0; i < n; ++i)
    { 
        int ad;
        scanf("%d", &ad);
        scanf("%d %d", &node[ad].data, &node[ad].nex);
    }
    int head = first, cnt = 1;
    vector<vector<int> > tmp;
    vector<int> tmp2, ans;
    while(head != -1)
    { 
        tmp2.push_back(head);
        if(cnt % k == 0 || node[head].nex == -1)
        { 
            tmp.push_back(tmp2);
            tmp2.clear();
        }
        cnt++;
        head = node[head].nex;
    }
    for(int i = tmp.size()-1; i >= 0; --i)
    { 
        for(int j = 0; j < tmp[i].size(); ++j)
        { 
            ans.push_back(tmp[i][j]);
        }
    }
    Print(ans);
    return 0;
}

3.　解法三（来源于网络）

#include<cstdio> 
#include<iostream> 
#include<vector> 
#include<map>
#include<string>
#include<set>
#include<cctype>
#include<algorithm>
using namespace std;
const int INF = 0x3fffffff;
const int maxn = 100010;
struct node{ 
    int address,data,next,flag;
    node(){ 
        flag = -1;
    }
}Node[maxn];
bool cmp1(node a,node b){ 
    return a.flag > b.flag;
}
bool cmp2(node a,node b){ 
    return a.flag < b.flag;
}
int main(){ 
    int start,n,k;
    scanf("%d%d%d",&start,&n,&k);
    for(int i = 0; i < n; i++){ 
        int add;
        scanf("%d",&add);
        scanf("%d%d",&Node[add].data,&Node[add].next);
        Node[add].address = add;
    }
    int cnt = 0;
    for(int p = start; p != -1; p = Node[p].next){ 
        Node[p].flag = cnt++;
    }
    sort(Node,Node+maxn,cmp1);
    int temp = cnt % k;
    if(temp != 0){ 
        sort(Node,Node+temp,cmp2);
    }
    for(int i = temp; i + k <= cnt; i+=k){ 
        sort(Node+i,Node+i+k,cmp2);
    }
    for(int i = 0; i < cnt; i++){ 
        if(i != cnt - 1)
            printf("%05d %d %05d\n",Node[i].address,Node[i].data,Node[i+1].address);
        else printf("%05d %d -1\n",Node[i].address,Node[i].data);
    }
}