1 题目
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.
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:
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 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
2 解析
- 题意：按照k个为一组，在组内倒着输出，如果那一组不足k个，则顺序输出
- 思路1：
- 1 创建静态链表（数据、地址、下一个结点地址、order（排序指标））
- 2 初始化所有结点的order为MAXN（即无效结点）
- 3 用题目给出的首地址，遍历整个链表，链表中的结点order按顺序赋值（赋count++，count初值为0）
- 4 用sort进行按order从小到大排序（前count个元素，为有效结点，并且为链表的初始顺序）
- 输出链表
- 如果用cnt来记录翻转小组的结点个数（每输出一组，cnt+k，cnt初值为0）
- 当cnt<= count时，小组内结点倒序输出；
- 当cnt>count时，小组内结点顺序输出；
- 在倒序输出中，如果当前结点为小组内最后一个结点
- a,同时cnt = count时，该结点的下一个结点地址输出-1
- b,同时cnt + k > count时 ,即下一个小组为顺序输出，小组内最后一个结点的下一个地址指向cnt，
- c,同时cnt + k < count时，即下一个小组为倒序输出，小组内最有一个结点的下一个地址指向cnt + k - 1 (因为数组下标比元素个数少一，因为数组下标从0开始)
- 在顺序输出中，特判如果当前输出的下标为count - 1,该结点的下一个地址输出-1
3 参考代码
思路一：
#include <cstdio>
#include <algorithm>using std::sort;const int MAXN = 100010;struct Node
{int m_address;int m_data;int m_next;int m_order;
}node[MAXN];bool cmp (Node a, Node b){return a.m_order < b.m_order;
}int main(int argc, char const *argv[])
{for (int i = 0; i != MAXN; ++i){node[i].m_order = 10 * MAXN;}int head, n, k;scanf("%d%d%d", &head, &n, &k);int address;while(n--){scanf("%d",&address);scanf("%d%d", &node[address].m_data, &node[address].m_next);node[address].m_address = address;}int count = 0;
for (int i = head; i != -1 ; i = node[i].m_next)
{node[i].m_order = count++ ;
}sort(node, node + MAXN, cmp);int cnt = 0;
for (int i = 0; i != count;)
{cnt += k;//计算翻转位数之和int temp = cnt - 1;//当前输出的位置if(cnt <= count){//如果没有超过总位数for (int j = 0; j != k; ++j){if(cnt == count && j == k - 1){//当为翻转的最后一个元素，且同时翻转数刚好等于总数printf("%05d %d -1\n", node[temp].m_address, node[temp].m_data);}else{if((j == k - 1) && (cnt + k > count)){//特殊处理翻转的最后一个元素，如果下一组元素为正常顺序printf("%05d %d %05d\n", node[temp].m_address, node[temp].m_data, node[cnt].m_address );}else if((j == k - 1) && (cnt + k <= count)){//特殊处理翻转的最后一个元素，如果下一组元素也为翻转元素printf("%05d %d %05d\n", node[temp].m_address, node[temp].m_data, node[cnt + k - 1].m_address );}else{//处理翻转元素（除最后一个元素）printf("%05d %d %05d\n", node[temp].m_address, node[temp].m_data, node[temp - 1].m_address );}}temp--;i++;}}else{//处理正常顺序的元素if(i != count - 1){printf("%05d %d %05d\n", node[i].m_address, node[i].m_data, node[i + 1].m_address );}else{printf("%05d %d -1\n", node[i].m_address, node[i].m_data);}i++;}}return 0;
}
思路二：
#include <cstdio>
#include <algorithm>using std::sort;const int MAXN = 100010;
struct Node{int m_address, m_data, m_next;int m_order;
}node[MAXN];bool cmp(Node a, Node b){return a.m_order < b.m_order;
}int main(){for (int i = 0; i != MAXN ; ++i) {node[i].m_order = MAXN;}int n ,k, begin;scanf("%d%d%d", &begin, &n, &k);int address;while(n--){scanf("%d", &address);scanf("%d%d", &node[address].m_data, &node[address].m_next);node[address].m_address = address;}int count = 0;for (int j = begin; j != -1 ; j = node[j].m_next) {node[j].m_order = count++;}sort(node, node + MAXN, cmp);n = count;for (int l = 0; l < n / k; ++l) {//枚举完n/k块for (int i = (l +1) * k -1; i > l * k ; --i) {//第l块倒着输出printf("%05d %d %05d\n", node[i].m_address, node[i].m_data, node[i -1].m_address);}//下面每一块是最后一个结点next的处理printf("%05d %d ", node[l * k].m_address, node[l * k].m_data);if(l < n/k -1){//如果不是最后一块，就指向下一个结点的最后一块printf("%05d\n", node[(l + 2) * k - 1].m_address);}else{if(n % k == 0){//恰好是最后一个结点输出-1printf("-1\n");}else{//剩下不完整的块，按顺序输出printf("%05d\n",node[(l+1)*k].m_address);for (int j = n / k * k; j < n; ++j) {printf("%05d %d ", node[j].m_address, node[j].m_data);if(j < n - 1){printf("%05d\n", node[j+1].m_address);}else{printf("-1\n");}}}}}return 0;
}