PAT 1075 链表元素分类(JAVA)_综合

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K 为 10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

输入格式：
每个输入包含一个测试用例。每个测试用例第 1 行给出：第 1 个结点的地址；结点总个数，即正整数N (≤10⁵) 以及正整数K (<=10³),结点的地址是 5 位非负整数，NULL 地址用 ?1 表示。

接下来有 N 行，每行格式为：

Address Data Next

其中 Address 是结点地址；Data 是该结点保存的数据，为 [?10⁵,10⁵]
?
?区间内的整数；Next 是下一结点的地址。题目保证给出的链表不为空。

输出格式：
对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

输出样例：
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

我的思路：这题和反转链表类似，利用数组存储值与下一个地址，利用list进行分类
（我5月份写的时候能AC的，现在有一个超时了）

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[]args)throws IOException{
    BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));int[]data=new int[100000];int[]next=new int[100000];String[]strs=bf.readLine().split(" ");int head=Integer.parseInt(strs[0]);int n=Integer.parseInt(strs[1]);int k=Integer.parseInt(strs[2]);for(int i=0;i<n;++i){
    String []curs=bf.readLine().split(" ");int ads=Integer.parseInt(curs[0]);data[ads]=Integer.parseInt(curs[1]);next[ads]=Integer.parseInt(curs[2]);}List<Integer>list1=new ArrayList<>();List<Integer>list2=new ArrayList<>();List<Integer>list3=new ArrayList<>();int cnt=0;while(head!=-1){
    if(data[head]<0)  list1.add(head);else if(data[head]<=k)list2.add(head);elselist3.add(head);head=next[head];cnt++;}list1.addAll(list2);list1.addAll(list3);for(int i=0;i<cnt-1;++i){
    int cur=list1.get(i),nextA=list1.get(i+1);System.out.printf("%05d %d %05d\n",cur,data[cur],nextA);}System.out.printf("%05d %d %d\n",list1.get(cnt-1),data[list1.get(cnt-1)],-1);}
}

java能AC的大佬救我