本文共 4016 字,大约阅读时间需要 13 分钟。
1074 Reversing Linked List (25分)
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.
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 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.
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.
00100 6 400000 4 9999900100 1 1230968237 6 -133218 3 0000099999 5 6823712309 2 33218
00000 4 3321833218 3 1230912309 2 0010000100 1 9999999999 5 6823768237 6 -1
第五测试点:答案错误原因是 存在一些不在头结点引出的链表上的结点。
我的代码:
收获:cout输出string可能超时
可以用printf 输出 格式:str.c_str()
#include#include
别人的代码:
#include#include using namespace std;int main() { int h, k, n, sum = 0;#ifdef _DEBUG ifstream cin("data.txt");#endif cin >> h >> n >> k; int temp, data[100005], next[100005], list[100005], result[100005]; for (int i = 0; i < n; i++) { cin >> temp; cin >> data[temp] >> next[temp]; } while (h != -1) { list[sum++] = h; h = next[h]; } for (int i = 0; i < sum; i++) result[i] = list[i]; for (int i = 0; i < (sum - sum % k); i++) result[i] = list[i / k * k + k - 1 - i % k]; for (int i = 0; i < sum - 1; i++) printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]); printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);#ifdef _DEBUG cin.close();#endif return 0;}
#include#include #include #include using namespace std;const int maxn = 1e5+100;int a[maxn],c[maxn];int b[maxn][2];int main(){ int digit,n,m; scanf("%d%d%d",&digit,&n,&m); for(int i = 1; i <= n; i++) { int x,y,z; scanf("%d%d%d",&x, &y, &z); b[x][0] = y; b[x][1] = z; } int gg = 0; a[++gg] = digit; for(++gg;a[gg-1] != -1;++gg) a[gg] = b[a[gg-1]][1]; gg--;gg--;// cout< < <= gg; i += m ) { for(int j = i; j > i-m; j--){ c[++now] = a[j]; } } if(i>gg){ for(i = i- m + 1; i <= gg;i++) c[++now] = a[i]; } for(int i = 1 ; i < gg;i++) printf("%05d %d %05d\n",c[i],b[c[i]][0],c[i+1]); printf("%05d %d %d\n",c[gg],b[c[gg]][0],-1); return 0;}
#include#include #include using namespace std;const int maxn = 1e5 + 10;struct Node { int add, data, next;}node[maxn];void init(){ for (int i = 0; i < maxn; i++)node[i].add = i;}int head, n, k;vector list;int main(){ scanf("%d%d%d", &head, &n, &k); init(); for (int i = 0; i < n; i++) { int address; scanf("%d", &address); scanf("%d%d", &node[address].data, &node[address].next); } int p = head; while (p != -1) { list.push_back(node[p]); p = node[p].next; } int group = list.size() / k; for (int i = 0; i < group; i++) { reverse(list.begin() + i*k, list.begin() + i*k + k); } for (int i = 0; i < list.size(); i++) { printf("%05d %d ", list[i].add, list[i].data); if (i != list.size() - 1)printf("%05d", list[i + 1].add); else printf("-1"); printf("\n"); } return 0;}
转载地址:http://xuven.baihongyu.com/