文章目錄
- 題目
- 輸入格式
- 輸出格式
- 輸入樣例
- 輸出樣例
- 題解
- 解題思路
- 完整代碼
編程練習題目集目錄
題目
??Given a constant K K K and a singly linked list L L L, you are supposed to reverse the links of every K K K elements on L L L. For example, given L being 1 → 2 → 3 → 4 → 5 → 6 1→2→3→4→5→6 1→2→3→4→5→6, if K = 3 K=3 K=3, then you must output 3 → 2 → 1 → 6 → 5 → 4 3→2→1→6→5→4 3→2→1→6→5→4; if K = 4 K=4 K=4, you must output 4 → 3 → 2 → 1 → 5 → 6 4→3→2→1→5→6 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 （ ≤ 1 0 5 ） N（≤10^5） N（≤105） which is the total number of nodes, and a positive K （ ≤ N ） K（≤N） 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 -1 ?1.
??Then N N 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
題解
解題思路
??使用兩個數組 d a t a data data 和 n e x t next next 分別存儲每個節點的數據和指向下一個節點的指針。從頭節點開始，按順序將節點的地址存儲在數組 l i s t list list 中，構建鏈表的順序結構。將 l i s t list list 中的節點按分組大小 K K K 進行反轉。將反轉后的節點順序存儲在結果數組 r e s u l t result result 中，即可。
完整代碼
#include <iostream>
using namespace std;int main(void) {int number, k, n, sum = 0;cin >> number >> n >> k;int temp, data[100005], next[1000005], list[100005], result[100005];// 讀取鏈表節點信息for (int i = 0; i < n; i++) {cin >> temp;cin >> data[temp] >> next[temp];}// 構建初始鏈表順序while (number != -1) {list[sum++] = number;number = next[number];}// 復制初始鏈表到結果數組for (int i = 0; i < sum; i++) result[i] = list[i];// 按照分組大小 K 反轉鏈表中的每個分組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]]);return 0;
}
)
