给定一个常数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个元素不反转。
[编程题]反转链表 (25)
- 热度指数：26480 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 146M，其他语言293M
- 算法知识视频讲解
输入描述:
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 105)、以及正整数K(<=N)，即要求反转的
子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。
接下来有N行，每行格式为：
Address Data Next
其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。
输出描述:
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
示例1
输入
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;
}
}
1.用Map<节点地址,节点>存储数据，
2.用List按连接顺序取出，
3.用新的List存储处理后的节点数据。
发表于 2019-09-05 21:57:01
回复(0)
TMD,这题真坑，看完题目立马有思路，写完代码死活AC不过，一直提示越界，后来看了讨论区才发现，TM有无效结点，实际结点会小于输入的n，草。前前后后磨蹭了近4小时，一下午就在这弄这题，***了。
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);
}
}
}
发表于 2019-08-17 18:26:49
回复(1)
这个题目实在是“一言难尽”，希望大家不要浪费太多时间在题目没有写出的坑上。如果你本地测试良好，但是线上不通过，检查以下坑：
- 题目输入可能包含无效节点，你需要自行遍历一遍链表来确定节点的真实数量
- 有效节点数可能小于 K，此时直接输出整个链表不要反转
- 有效节点数可能小于等于 2，此时也是直接输出（对应第7个检查点）
贴个通过全部测试点的代码，为了处理上面的坑加了一些莫名其妙的判断，大家理解一下。
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);
}
}
}
发表于 2019-06-22 22:37:34
回复(0)
//注意：输入的可能不止一个链表！！！即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"); } }
编辑于 2018-11-30 15:54:10
回复(0)
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;
}
} 内存超限超限，心态崩了，弃题。
发表于 2017-08-20 16:08:52
回复(0)
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; }
发表于 2017-01-26 14:31:12
回复(1)
问题信息
难度：
7条回答
142收藏
25756浏览
通过挑战的用户
-
2023-03-08 17:02:43
-
2023-03-08 10:03:18
-
2023-03-05 13:22:42 -
2023-03-04 21:42:51 -
2023-03-02 01:24:15
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
