长沙做网站排名/外贸网站平台有哪些
1025 反转链表 (25分)
给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。
输入格式：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤105)、以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。
接下来有 N 行，每行格式为：
Address Data Next
其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：
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
此题困难在于所给定的单链表结点中，包含有我们用不上的游离结点，游离结点应该过滤掉，不应该输出。
同时，有游离结点意味着单链表的结点个数不一定等于题目所给定的结点 总个数，故单链表的结点总个数需要重新单独统计。
PS：在C++的环境下，测试点5的用时明显高于其他测试点，推测是数据量较大的测试，统计了其他人的python 程序在测试点5的结果，都是超时，所以又是喜闻乐见的python效率低环节（手动滑稽）。
在python代码后贴一份C++代码。
python代码（测试点5超时，不过好歹思路是对的，哈哈）：
#开始的地址，链表节点数量，K
start_address,count,k=list(map(int,input().split(' ')))
#创建一个长度为10万的空列表
single_lists=[None]*100000
#读取输入，并存放至空列表中
for i in range(count):single_list=input().split(' ')single_lists[int(single_list[0])]=single_list#用来存放列表排好序的单链表
result_lists=[]#注意：
#题目给定的结点中，包含游离的结点
#游离的结点不输出
#在下个while循环中，游离的结点会被排除
#所以需要重新统计结点数量count=0
#将结点按顺序排成单链表
while True:count=count+1result_lists.append(single_lists[start_address])start_address=int(single_lists[start_address][2])if start_address==-1:breakflag=0if k!=0:#按要求将单链表进行部分逆置while (flag+k)<=count:flag=flag+kreverse_result_lists=result_lists[flag-k:flag]result_lists[flag - k:flag]=reverse_result_lists[::-1]#按要求输出单链表
for j in range(count-1):result_lists[j][2]=result_lists[j+1][0]print(' '.join(result_lists[j]))
result_lists[-1][2]='-1'
print(' '.join(result_lists[-1]))大佬的C++代码：
链接：https://blog.csdn.net/zhanggirlzhangboy/article/details/83065414
C++代码：
#include <iostream>
#include <vector>using namespace std;const int MAX = 100000;struct node {int id;int data;int next;
};int main() {int start, n, k;scanf("%d %d %d", &start, &n, &k);node nodeArray[MAX];for(int i=0; i<n; i++) {int id, data, next;scanf("%d %d %d", &id, &data, &next);nodeArray[id].id = id;nodeArray[id].data = data;nodeArray[id].next = next;}//original ordervector<node> v;int now = start;for(int i=0; i<n; i++) {if(now!=-1) {v.push_back(nodeArray[now]);now = nodeArray[now].next;}}//reverse ordervector<node> v2;int startPos = 0;while(startPos+k<=v.size()) {for(int i=startPos+k-1; i>=startPos; i--) {node tmp = v.at(i);v2.push_back(tmp);}startPos += k;}while(startPos<v.size()) {v2.push_back(v.at(startPos++));}for(int i=0; i<v2.size()-1; i++) {node t = v2.at(i);node tNext = v2.at(i+1);printf("%05d %d %05d\n", t.id, t.data, tNext.id);}printf("%05d %d -1\n", v2.at(v2.size()-1).id, v2.at(v2.size()-1).data);return 0;
}