给定一个单链表 L,我们将每 K 个结点看成一个区块(链表最后若不足 K 个结点,也看成一个区块),请编写程序将 L 中所有区块的链接反转。例如:给定 L 为 1→2→3→4→5→6→7→8,K 为 3,则输出应该为 7→8→4→5→6→1→2→3。
输入格式:
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤105)、以及正整数 K (≤N),即区块的大小。结点的地址是 5 位非负整数,NULL 地址用 −1 表示。
接下来有 N 行,每行格式为:
Address Data Next
其中 Address
是结点地址,Data
是该结点保存的整数数据,Next
是下一结点的地址。
输出格式:
对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。
输入样例:
00100 8 3 71120 7 88666 00000 4 99999 00100 1 12309 68237 6 71120 33218 3 00000 99999 5 68237 88666 8 -1 12309 2 33218
输出样例:
71120 7 88666 88666 8 00000 00000 4 99999 99999 5 68237 68237 6 00100 00100 1 12309 12309 2 33218 33218 3 -1
代码实现:
import java.io.*; import java.util.ArrayList; /** * @author yx * @date 2022-07-29 1:32 */ public class Main { static PrintWriter out=new PrintWriter(System.out); static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer in=new StreamTokenizer(ins); static class Node{ int Address; int Data; int Next; Node(int Address,int Data,int Next){ this.Address=Address; this.Data=Data; this.Next=Next; } } public static void main(String[] args) throws IOException { in.nextToken(); int initAddress=(int) in.nval; in.nextToken(); int N=(int) in.nval; in.nextToken(); int K=(int) in.nval; ArrayList<Node> list=new ArrayList<>();//原始链表 ArrayList<Node> list1=new ArrayList<>();//区块反转链表 Node[] nums=new Node[100000];//初始化数组 for (int i = 0; i < N; i++) { in.nextToken(); int address=(int) in.nval; in.nextToken(); int data=(int) in.nval; in.nextToken(); int next=(int) in.nval; nums[address]=new Node(address,data,next); } //按序串成一个链表 while (initAddress!=-1){ list.add(nums[initAddress]); initAddress=nums[initAddress].Next; } // for (int i = 0; i < list.size(); i++) { // System.out.println(list.get(i).Address+" "+list.get(i).Data+" "+list.get(i).Next); // } int temp=list.size()/K; int yu=list.size()%K; //区块反转 if(yu==0){ for (int i = temp; i >0; i--) { for (int j = (i-1)*K; j <i*K ; j++) { list1.add(list.get(j)); } } }else { for (int i = temp*K; i <list.size() ; i++) { list1.add(list.get(i)); } for (int i = temp; i >0; i--) { for (int j = (i-1)*K; j <i*K ; j++) { list1.add(list.get(j)); } } } //类似于NO1025可以卡bug for (int i = 0; i < list1.size()-1; i++) { out.printf("%05d %d %05d\n",list1.get(i).Address,list1.get(i).Data,list1.get(i+1).Address); } out.printf("%05d %d -1\n",list1.get(list1.size()-1).Address,list1.get(list1.size()-1).Data); out.flush(); } }
编辑