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→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

给定一个常数 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 个元素不反转。

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 (≤10​5​​) which is the total number of nodes, and a positive K (≤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:

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤10​5​​)、以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。

接下来有 N 行，每行格式为：

Address Data Next

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

其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。

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 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

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

解题思路

1. 初始化并读入链表；
2. 从头节点开始遍历链表，找出其中有效节点并标记；
3. 有效节点按照翻转规则对其重新编号；
4. 重新排序；
5. 按照题目格式要求输出返回零值。

代码

#include<cstdio>
#include<algorithm>
using namespace std;

#define maxn 100010
#define INF 100000000

struct Node{
    int id;
    int data;
    int next;
    int seq;
    int vis;
}node[maxn];

int FN,N,K;
int num=0,current;

bool cmp(Node a,Node b){
    if(a.vis!=b.vis){
        return a.vis>b.vis;
    }else{
        return a.seq<b.seq;
    }
}
void Init(){
    int i; 
    int ad;
    scanf("%d%d%d",&FN,&N,&K);
    for(i=0;i<N;i++){
        scanf("%d",&ad);
        node[ad].id=ad;
        scanf("%d%d",&node[ad].data,&node[ad].next);
    }
}

int main(){
    int group; 
    int i,j;
    Init();
    current=FN;
    while(current!=-1){
        node[current].vis=1;
        node[current].seq=num++;
        current=node[current].next;
    }//编号从0开始 
    group=num/K;
    current=FN;
    for(i=0;i<group;i++){
        for(j=K-1;j>=0;j--){
            node[current].seq=i*K+j;
            current=node[current].next;
        }
    }
    sort(node,node+maxn,cmp);
    printf("%05d %d ",node[0].id,node[0].data);
    for(i=1;i<num;i++){
        printf("%05d\n%05d %d ",node[i].id,node[i].id,node[i].data);
    }
    printf("-1\n");
    return 0;
}

运行结果