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 4
- 00000 4 99999
- 00100 1 12309
- 68237 6 -1
- 33218 3 00000
- 99999 5 68237
- 12309 2 33218
- 00000 4 33218
- 33218 3 12309
- 12309 2 00100
- 00100 1 99999
- 99999 5 68237
- 68237 6 -1
和乙级的1025一样:1025 反转链表 (25 分)_Brosto_Cloud的博客-CSDN博客
Data 和 Next 数组的下标 i 都是地址,表示对应地址的数据和链接的下一个地址,list数组下标 i 是顺序,代表节点地址,每个地址对应的数据都是不变的,改变的只是链接的下一个地址,所以对list 数组每k个进行反转后直接输出 list[i]和list[i+1]就是对应的地址顺序,data[i]是对应的数据。
- #include
- #include
- #include
- using namespace std;
- int Data[100010], list[100010], Next[100010];
- int n, k, addr, t, sum;
-
- int main() {
- cin >> addr >> n >> k;
- for (int i = 0; i < n; i++) {
- cin >> t;
- cin >> Data[t] >> Next[t];
- }
- while (addr != -1) {
- list[sum++] = addr;
- addr = Next[addr];
- }
- for (int i = 0; i < (sum - sum % k); i += k) {
- reverse(list + i, list + i + k);
- }
- for (int i = 0; i < sum - 1; i++) {
- cout << setfill('0') << setw(5) << list[i] << ' ' << Data[list[i]] << ' ' << setfill('0') << setw(
- 5) << list[i + 1] << endl;
- }
- cout << setfill('0') << setw(5) << list[sum - 1] << ' ' << Data[list[sum - 1]] << ' ' << -1;
- return 0;
- }