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.
目录
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 33218 3 00000 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
Python 的代码在第五个测试点“ 最大N,最后剩K-1不反转 ”,运行超时。C++代码可以AC。
思路相同, 先读取有效的数据,排除不在链表上的节点 ,然后用有序列表的部分反转操作达到反转。Python效率不如C++,C++用4ms算完的,Python要22ms,最大长度C++花了200多ms,而这题限制400ms。也想不出优化的地方了。
编译器:Python(python3)
d={} start_addr, L, K = input().split(' ') L = int(L) K = int(K) for i in range(L): addr1, data, next_addr = input().split(' ') d[addr1] = [data,next_addr] addr_list = [] count = 0 temp_addr = start_addr for i in range(L): if temp_addr == '-1': break else: count += 1 addr_list.append(temp_addr) temp_addr = d[temp_addr][1] res_index = 0 while(res_index + K <= count): sub_list = addr_list[res_index:res_index+K] addr_list[res_index:res_index+K] = sub_list[::-1] res_index += K for i in range(len(addr_list) - 1): print(addr_list[i],d[ addr_list[i] ][0],addr_list[i+1]) print(addr_list[-1],d[ addr_list[-1] ][0],'-1')
编译器:C++(g++)
#include <iostream> #include <algorithm> #define MAXSIZE 100000 using namespace std; struct LNode { int data; int next; }node[MAXSIZE]; int List[MAXSIZE]; int main() { int head_addr, n, k; cin >> head_addr >> n >> k; int addr, data, next; for(int i = 0; i < n; i++) { cin >> addr; cin >> data; cin >> next; node[addr].data = data; node[addr].next = next; } int count = 0; int p_next = head_addr; while(p_next!=-1) { List[count] = p_next; p_next = node[p_next].next; count = count + 1; } int first = 0; while (first + k <= count) { reverse(&List[first], &List[first + k]); first += k; } for(first = 0; first < count-1; first++) printf("%05d %d %05d\n", List[first], node[List[first]].data, List[first + 1]); printf("%05d %d -1\n", List[first], node[List[first]].data); return 0; }