一、题目
给定一个常数 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二、解析
这题可以偷懒，倒序后先改变在数组中的位置，不用更新每一个节点的next值就能正常输出了。有坑，不一定所有节点都有效。第五个测试点不用水桶法会超时。第六个测试点需要考虑并不是所有节点都有效。用正常的思维来说，先用一个list来存储所有节点，然后二重循环遍历这个list，把乱序的整成连续的，并用另外一个list存起来。但是这样第五个测试点是超时的。
三、代码
java 超时版：
查看代码
查看代码
package org.example.shuati;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class PAT_basic_1025 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split("\\s+");
String start = str[0];
int n = Integer.parseInt(str[1]);
int k = Integer.parseInt(str[2]);
ArrayList<Node> list = new ArrayList<>();
Node root = new Node();
for (int i = 0; i < n; i++) {
String[] s = br.readLine().split("\\s+");
Node newNode = new Node(s[0], Integer.parseInt(s[1]), s[2]);
if(s[0].equals(start))
root = newNode;
list.add(newNode);
}
Node[] lList = new Node[n];
lList[0] = root;
Node cur = root;
int effectiveNode = 1;
for (int i = 1; i < n; i++) {
for (Node node : list) {
if(node.address.equals(cur.next)){
lList[i] = node;
cur = node;
effectiveNode++;
break;
}
}
}
for(int i=0; i<effectiveNode; i+=k){
if(i+k > effectiveNode) break;
for(int j=i,p=i+k-1; j<p; j++,p--){
Node temp = lList[j];
lList[j] = lList[p];
lList[p] = temp;
}
}
for(int i=0; i<effectiveNode; i++){
if(i+1 < effectiveNode)
System.out.printf("%s %d %s\n", lList[i].address, lList[i].data, lList[i+1].address);
else
System.out.printf("%s %d -1", lList[i].address, lList[i].data);
}
}
static class Node{
private String address;
private int data;
private String next;
public Node() {
}
public Node(String address, int data, String next) {
this.address = address;
this.data = data;
this.next = next;
}
public String getAddress() {
return address;
}
public void setAddress(String address) {
this.address = address;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public String getNext() {
return next;
}
public void setNext(String next) {
this.next = next;
}
}
}
c++超时版，用c++改写上面的java版本仍然是超时的，将无序的输入连成一个有序的链表的二重循环花了太多时间：
查看代码
查看代码
//
// Created by yaodong on 2023/2/18.
//
#include <vector>
#include "iostream"
using namespace std;
class Node{
public:
int address,data,next;
Node(int address, int data, int next) : address(address), data(data), next(next) {}
Node() {}
};
int main(){
int initAddress, n, k;
cin>>initAddress>>n>>k;
vector<Node> vec;
Node lList[n];
Node root;
int add,data,next;
for(int i=0; i<n; i++){
cin>>add>>data>>next;
Node newNode = Node(add, data, next);
if(add == initAddress)
root = newNode;
vec.push_back(newNode);
}
lList[0] = root;
Node cur = root;
//有效节点，不一定所有的输入都有效
int eNode = 1;
for (int i = 1; i < n; ++i) {
for (auto item: vec){
if(item.address == cur.next){
lList[i] = item;
cur = item;
eNode++;
break;
}
}
}
for(int i=0; i<eNode; i+=k){
if(i+k > eNode) break;
for(int j=i,p=i+k-1; j<p; j++,p--){
Node temp = lList[j];
lList[j] = lList[p];
lList[p] = temp;
}
}
for(int i=0; i<eNode; i++){
if(i+1 < eNode)
printf("%05d %d %05d\n", lList[i].address, lList[i].data, lList[i+1].address);
else
printf("%05d %d -1", lList[i].address, lList[i].data);
}
return 0;
}
c++ AC版，用水桶法，仔细想想，水桶法也是合理的，因为实际生活中，地址位数肯定是一样的，但是题目没有说明，每一个测试用例都是5位。或许其实连这个也应该想到的。至少猜一下。
//
// Created by yaodong on 2023/2/18.
//
#include "iostream"
using namespace std;
int main(){
int initAddress, n, k;
cin>>initAddress>>n>>k;
int list[100001], data[100001], next[100001];
int index;
for(int i=0; i<n; i++){
cin>>index;
cin>>data[index]>>next[index];
}
//不一定所有节点都有效
int eNode = 0;
int nextAdd = initAddress;
while(nextAdd != -1){
list[eNode++] = nextAdd;
nextAdd = next[nextAdd];
}
for(int i=0; i<eNode; i+=k){
if(i+k > eNode) break;
for(int j=i,p=i+k-1; j<p; j++,p--){
int temp = list[j];
list[j] = list[p];
list[p] = temp;
}
}
for(int i=0; i<eNode; i++){
if(i+1 < eNode)
printf("%05d %d %05d\n", list[i], data[list[i]], list[i+1]);
else
printf("%05d %d -1", list[i], data[list[i]]);
}
}标签：1025,Node,PAT,int,list,next,链表,java,data From： https://www.cnblogs.com/langweixianszu/p/17133760.html