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.
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:Sample Output: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
71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1
这题是很基础的链表问题,对于这种问题,我一般喜欢写链式前向星,不喜欢指针形式,复杂且指的头疼。
直接先全部翻转,然后分组翻转即可。
注意:最后一部分不足k的话也是需要翻转的。
#include
#include
#include
#include
using namespace std;
const int N = 100010;
int n, k;
int h, e[N], ne[N];
int main()
{
scanf("%d%d%d", &h, &n, &k);
for (int i = 0; i < n; i ++ )
{
int address, data, next;
scanf("%d%d%d", &address, &data, &next);
e[address] = data, ne[address] = next;
}
vector q;
for (int i = h; i != -1; i = ne[i]) q.push_back(i);
int size = q.size() % k; // 这一步必须思考清晰,取余则是多余数据
// size / k 则是你有几个block
reverse(q.begin(), q.end());
bool flag = true;
for(int i = 0; i < q.size(); )
{
if (flag) reverse(q.begin() + i, q.begin() + i + size), i += size, flag = false;
else
{
reverse(q.begin() + i, q.begin() + i + k);
i += k;
}
}
for (int i = 0; i < q.size(); i ++ )
{
printf("%05d %d ", q[i], e[q[i]]);
if (i + 1 == q.size()) puts("-1");
else printf("%05d\n", q[i + 1]);
}
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)