题目

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=3K = 3K=3, then you must output 3→2→1→6→5→4; if K=4K = 4K=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(≤ 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.

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 99999 5 68237 12309 2 33218

Sample Output:

00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1

注意

supposed to reverse the links of every K elements on L（反转每k个数）The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1

解法1：利用空间换时间

定义一个长10000数组，下标表示每行的Address值。根据结点的顺序，依次加入到一个vector中。对vector中的每个K元素进行反转。输出最终结果 #include <iostream> #include <vector> using namespace std; #define MAX_ADDRESS_SIZE 100000 struct Node { int Address = -1; int Data = 0; int Next = -1; }; void reverse_linked_nodes(vector<Node>& list, int start, int end) { while (start < end) { Node temp = list[start]; list[start] = list[end]; list[end] = temp; start++; end--; } } int main() { // read first command line int head_addr, node_count, reverse_node_count; cin >> head_addr >> node_count >> reverse_node_count; // read list nodes vector<Node> nodes(MAX_ADDRESS_SIZE); for (int i = 0; i < node_count; i++) { int addr, data, next; cin >> addr >> data >> next; nodes[addr].Address = addr; nodes[addr].Data = data; nodes[addr].Next = next; } // insert to vector with sorted vector<Node> node_list; node_list.push_back(nodes[head_addr]); // push the first node while (node_list.back().Next != -1) { node_list.push_back(nodes[node_list.back().Next]); //push the next node } // reverse every reverse_count elements of real link list int reverse_times = node_list.size() / reverse_node_count; for (int i = 0; i < reverse_times; i++) { int start = i * reverse_node_count; int end = start + reverse_node_count -1; reverse_linked_nodes(node_list, start, end); } // output result for (int i = 0; i < node_list.size()-1; i++) { printf("%05d %d %05d\n", node_list[i].Address, node_list[i].Data, node_list[i+1].Address); } printf("%05d %d %d\n", node_list.back().Address, node_list.back().Data, -1); return 0; }