给定两个单链表 L1=a1→a2→⋯→an−1→an 和 L2=b1→b2→⋯→bm−1→bm。如果 n≥2m，你的任务是将比较短的那个链表逆序，然后将之并入比较长的那个链表，得到一个形如 a1→a2→bm→a3→a4→bm−1⋯ 的结果。例如给定两个链表分别为 6→7 和 1→2→3→4→5，你应该输出 1→2→7→3→4→6→5。
输入格式：
输入首先在第一行中给出两个链表 L1 和 L2 的头结点的地址，以及正整数
N (≤105)，即给定的结点总数。一个结点的地址是一个 5 位数的非负整数，空地址 NULL 用 -1 表示。
随后 N 行，每行按以下格式给出一个结点的信息：
Address Data Next
其中 Address 是结点的地址，Data 是不超过 105 的正整数，Next 是下一个结点的地址。题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。
输出格式：
按顺序输出结果链表，每个结点占一行，格式与输入相同。
输入样例：
00100 01000 7 02233 2 34891 00100 6 00001 34891 3 10086 01000 1 02233 00033 5 -1 10086 4 00033 00001 7 -1
输出样例：
01000 1 02233 02233 2 00001 00001 7 34891 34891 3 10086 10086 4 00100 00100 6 00033 00033 5 -1
代码实现：
import java.io.*; import java.util.ArrayList; /** * @author yx * @date 2022-07-28 22:39 */ 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){ Address=address; Data=data; Next=next; } } public static void main(String[] args) throws IOException { in.nextToken(); int l1_initAddress=(int) in.nval; in.nextToken(); int l2_initAddress=(int) in.nval; in.nextToken(); int N=(int) in.nval; ArrayList<Node> list1=new ArrayList<>();//L1链表 ArrayList<Node> list2=new ArrayList<>();//L2链表 ArrayList<Node> ans=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); } //初始化L1 while (l1_initAddress!=-1){ list1.add(nums[l1_initAddress]); l1_initAddress=nums[l1_initAddress].Next; } // for (int i = 0; i < list1.size(); i++) { // System.out.println(list1.get(i).Address+" "+list1.get(i).Data+" "+list1.get(i).Next); // } //初始化L2 while (l2_initAddress!=-1){ list2.add(nums[l2_initAddress]); l2_initAddress=nums[l2_initAddress].Next; } // for (int i = 0; i < list2.size(); i++) { // System.out.println(list2.get(i).Address+" "+list2.get(i).Data+" "+list2.get(i).Next); // } if(list1.size()>=2*list2.size()){ //逆序 for (int i = 0,j=list2.size()-1; i < j; i++,j--) { Node temp=list2.get(j); list2.set(j,list2.get(i)); list2.set(i,temp); } int flag1=0; int flag2=0; for (int i = 0; i < list1.size(); i++) { ans.add(list1.get(i)); flag1++; if(flag1%2==0&&flag2<list2.size()){ ans.add(list2.get(flag2)); flag2++; } } }else { //逆序 for (int i = 0,j=list1.size()-1; i < j; i++,j--) { Node temp=list1.get(j); list1.set(j,list1.get(i)); list1.set(i,temp); } // for (int i = 0; i < list1.size(); i++) { // System.out.println(list1.get(i).Address+" "+list1.get(i).Data+" "+list1.get(i).Next); // } int flag1=0; int flag2=0; for (int i = 0; i < list2.size(); i++) { ans.add(list2.get(i)); // System.out.println(ans.get(i).Address); flag1++; if(flag1%2==0&&flag2<list1.size()){ ans.add(list1.get(flag2)); flag2++; } } } for (int i = 0; i < ans.size()-1; i++) { // System.out.println(1); out.printf("%05d %d %05d\n",ans.get(i).Address,ans.get(i).Data,ans.get(i+1).Address); } out.printf("%05d %d -1\n",ans.get(ans.size()-1).Address,ans.get(ans.size()-1).Data); //这个输出流一定要记得关 out.flush(); } }
编辑
