给定一个常数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<br/>00000 4 99999<br/>00100 1 12309<br/>68237 6 -1<br/>33218 3 00000<br/>99999 5 68237<br/>12309 2 33218
00000 4 33218<br/>33218 3 12309<br/>12309 2 00100<br/>00100 1 99999<br/>99999 5 68237<br/>68237 6 -1
package pat.t0905; import java.util.*; public class T1015 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Map<String, Node> map = new HashMap<>(); String beginAddr = sc.next();// 首地址 int nodeCount = sc.nextInt();// 节点总数 int groupSize = Integer.parseInt(sc.nextLine().trim()); for (int i = 0; i < nodeCount; i++) { String[] line = sc.nextLine().split(" "); Node node = new Node(line[0], line[1], line[2]); map.put(line[0], node); } String addr = beginAddr; List<Node> list = new ArrayList<>(); while (!"-1".equals(addr)) { Node node = map.get(addr); if (node == null) { break; } addr = node.next; list.add(node); } List<Node> list2 = new ArrayList<>();// 排序好存在新列表中 for (int i = 1; i * groupSize <= list.size(); i++) { for (int j = 0; j < groupSize; j++) { list2.add(list.get(i * groupSize - j - 1)); } } int rest = list.size() % groupSize; for (int i = list.size() - rest; i < list.size(); i++) { list2.add(list.get(i)); } for (int i = 0; i < list2.size() - 1; i++) { list2.get(i).next = list2.get(i + 1).address; } list2.get(list2.size() - 1).next = "-1"; for (Node node : list2) { System.out.println(node); } sc.close(); } } class Node { String address; String data; String next; public Node(String address, String data, String next) { this.address = address; this.data = data; this.next = next; } public String toString() { return address + " " + data + " " + next; } }
package test; import java.util.*; public class Main{ static class Node{ String address; String value; String next; public Node(String address, String value, String next) { this.address = address; this.value = value; this.next = next; } } public static void main(String[] args){ Scanner sc = new Scanner(System.in); String start = sc.next(); String temp= ""; int n = sc.nextInt(); int k = sc.nextInt(); HashMap<String, Node> map = new HashMap<String, Node>(n); for(int i = 0; i < n; i++){ temp = sc.next(); map.put(temp, new Node(temp, sc.next(), sc.next())); } int count = 0;//记录真实结点数目 Node [] nodes = new Node[n]; Node p = map.get(start); while(p != null){ nodes[count++] = p; //真实结点就放入数组 p = map.get(p.next); } p = map.get(start); if(count <= 2 || count < k){ //结点数小于等于2 或者真实结点数小于k直接输出 for (int i = 0; i < count; i++) { System.out.println(nodes[i].address + " " + nodes[i].value + " " + nodes[i].next); } return; } n = count; //一开始没有意识到有无效结点,就一直以输入的n做结点数,结果疯狂越界 int i = k - 1; for(; i < n - (n % k); i += k){ for(int j = i; j > i - k; j--){ if(j == i - k + 1){ if(i + k < n) System.out.println(nodes[j].address + " " + nodes[j].value + " " + nodes[i + k].address); else System.out.println(nodes[j].address + " " + nodes[j].value + " " + nodes[i + 1].address); }else System.out.println(nodes[j].address + " " + nodes[j].value + " " + nodes[j - 1].address); } } i -= k; for(++i; i < n; i++){ System.out.println(nodes[i].address + " " + nodes[i].value + " " + nodes[i].next); } } }
这个题目实在是“一言难尽”,希望大家不要浪费太多时间在题目没有写出的坑上。如果你本地测试良好,但是线上不通过,检查以下坑:
贴个通过全部测试点的代码,为了处理上面的坑加了一些莫名其妙的判断,大家理解一下。
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); HashMap<String, Node> nodes = new HashMap<String, Node>(); String beginAddress = in.next(); int nodeNum = in.nextInt(); int K = in.nextInt(); for(int i = 0; i< nodeNum; i++) { String address = in.next(); int data = in.nextInt(); String nextAddress = in.next(); nodes.put(address, new Node(address, data, nextAddress)); } int validenodeNum = 0; Node countNode = nodes.get(beginAddress); while(countNode != null) { countNode = countNode.next(nodes); validenodeNum++; } Node judgeNdde = nodes.get(beginAddress); if(validenodeNum <= 2 || validenodeNum < K) { while(judgeNdde!=null) { System.out.println(judgeNdde); judgeNdde = judgeNdde.next(nodes); } return; } Node prev = nodes.get(beginAddress); Node current = prev.next(nodes); Node next = current.next(nodes); Node beginNode = prev; Node prevBeginNode = null; Node printNode = null; while(validenodeNum >= K) { for(int i = 2; i < K; i++) { current.nextAddress = prev.address; prev = current; current = next; next = next.next(nodes); } current.nextAddress = prev.address; if(printNode == null) printNode = current; if(prevBeginNode == null) { prevBeginNode = beginNode; } else { prevBeginNode.nextAddress = current.address; prevBeginNode = beginNode; } if(next == null) { beginNode.nextAddress = "-1"; break; } beginNode.nextAddress = next.address; prev = next; current = prev.next(nodes); next = current.next(nodes); beginNode = prev; validenodeNum -= K; } while(printNode != null) { System.out.println(printNode); printNode = printNode.next(nodes); } } static class Node { String address = ""; int data = 0; String nextAddress = ""; public Node(String address, int data, String nextAddress) { this.address = address; this.data = data; this.nextAddress = nextAddress; } @Override public String toString() { return address + " " + data + " " + nextAddress; } public Node next(HashMap<String, Node> nodes) { return nodes.get(nextAddress); } } }
//注意:输入的可能不止一个链表!!!即N不一定是需要反转链表的长度 import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String firstAddress = scanner.next(); int N = scanner.nextInt(); int K = scanner.nextInt(); if (N > 100000) N = 100000; HashMap<String, String> addressmap = new HashMap<>(); HashMap<String, String> datamap = new HashMap<>(); for (int i = 0; i < N; i++) { String address = scanner.next(); String data = scanner.next(); String next = scanner.next(); addressmap.put(address, next); datamap.put(address, data); } List<String> addressList = new ArrayList<>(); String address = firstAddress; while (!address.equals("-1")) { addressList.add(address); address = addressmap.get(address); } int len=addressList.size(); int count = len / K; String[][] res = new String[len][2]; int num = 0; while (count > 0) { int p = num; for (int i = num + K - 1; i >= num; i--) { String addr = addressList.get(i); res[p][0] = addr; res[p][1] = datamap.get(addr); p++; } num += K; count--; } for (int j = num; j < len; j++) { String addr = addressList.get(j); res[j][0] = addr; res[j][1] = datamap.get(addr); } for (int x = 0; x < len- 1; x++) { System.out.println(res[x][0] + " " + res[x][1] + " " + res[x + 1][0]); } System.out.println(res[len- 1][0] + " " + res[len- 1][1] + " -1"); } }
package pat15; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); Node n=null; int first=input.nextInt(); int count=input.nextInt(); int size=input.nextInt(); Node[] nrr=new Node[100002]; nrr[100001]=new Node(0, 0, first); int ad=0; int data=0; int next=0; int arr=0; for(int i=0;i<count;i++){ ad=input.nextInt(); data=input.nextInt(); next=input.nextInt(); if(ad<1000000 && next <1000000){ nrr[ad]=new Node(ad, data, next); arr++; } } int j=0; int i=100001; for(j=arr/size;j>0 && i!=-1;j--) i=reverse(nrr,i,size); String nt=""; String nts=""; int key=nrr[100001].next; while(key!=-1){ n=nrr[key]; nt=tackbak(n.ad); nts=tackbak(n.next); System.out.println(nt+" "+n.data+" "+nts); key=nrr[key].next; } } private static int reverse(Node[] nrr, int head, int size) { int wei=nrr[head].next; int oldone=nrr[head].next; int p=0; //尾 for(int j=0;j<size && wei!=-1;j++ ){ wei=nrr[wei].next; } nrr[head].next=wei; for(int j=0;j<size && oldone!=-1;j++){ p=nrr[oldone].next; nrr[oldone].next=nrr[head].next; nrr[head].next=oldone; oldone=p; } return oldone; } private static String tackbak(int ad) { String str=ad+""; if(ad!=-1){ while(str.length()<5) str="0"+str;} return str; } } class Node{ public int ad; public int data; public int next; public Node(int ad, int data, int next) { super(); this.ad = ad; this.data = data; this.next = next; } }内存超限超限,心态崩了,弃题。
import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] fline = sc.nextLine().split(" "); //因为结点不是按顺序输入,哈希表用来辅助建造链表 HashMap<String, Node> map = new HashMap<>(); //root作为头结点 Node root = new Node(null, null); root.ad = "first"; Node n = new Node(fline[0], null); root.next = n; map.put("first",root); map.put(fline[0], n); int N = Integer.parseInt(fline[1]); int K = Integer.parseInt(fline[2]); //构建链表 for (int i = 0; i < N; i++) { String[] line = sc.nextLine().split(" "); Node node; Node next = null; if (map.containsKey(line[0])) { node = map.get(line[0]); } else { node = new Node(line[0], null); } if (!line[2].equals("-1")) { if (map.containsKey(line[2])) { next = map.get(line[2]); } else { next = new Node(line[2], null); } } node.next = next; node.data = line[1]; map.put(line[0], node); map.put(line[2], next); } //遍历链表进行翻转 Node p = root.next; Node pre = root; Node temp = null; int count = 0; while (p != null) { count ++; Node pnext = p.next; p.next = temp; temp = p; if (count == K) { count = 0; Node q = pre.next; pre.next = temp; q.next = pnext; temp = null; pre = q; } p = pnext; } pre.next = null; if (temp != null) { p = temp; while (p != null) { temp = p.next; p.next = pre.next; pre.next = p; p = temp; } } //遍历链表进行输出 p = root.next; while (p != null) { Node next = p.next; System.out.print(p.ad + " " + p.data + " "); if (next != null) { System.out.println(next.ad); } else { System.out.println("-1"); } p = next; } } } class Node { Node(String ad, Node next) { this.ad = ad; this.next = next; } String data = null; String ad = null; Node next = null; }