2019-03-01-PAT乙级-1025-反转链表

2019-03-01-PAT乙级-1025-反转链表

2019-03-01-PAT乙级-1025-反转链表

原文链接:PAT乙级-1025-反转链表

github代码地址:HibisciDai/OJ-PAT-ACM

2019-03-01-PAT乙级-1025-反转链表

编程描述

给定一个常数 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
2
3
4
5
作者: CHEN, Yue
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB

输入格式

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤ $10^{5}$)、以及正整数 K (≤N),即要求反转的子链结点的个数。结点的地址是 5 位非负整数,NULL 地址用 −1 表示。

接下来有 N 行,每行格式为:

1
Address Data Next

其中 Address 是结点地址,Data 是该结点保存的整数数据,Next 是下一结点的地址。

输出格式

对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。

输入样例

1
2
3
4
5
6
7
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例

1
2
3
4
5
6
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

算法实现

JAVA(openjdk)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
public static class Node {
int address;
int data;
int next;

public Node() {
super();
}

public Node(int address, int data, int next) {
super();
this.address = address;
this.data = data;
this.next = next;
}

@Override
public String toString() {
System.out.printf("%05d", address);
System.out.print(" " + data + " ");
if (next == -1) {
System.out.print(-1);
} else {
System.out.printf("%05d", next);
}
return "";
}
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int first = sc.nextInt();
int N = sc.nextInt();
int K = sc.nextInt();
ArrayList<Node> list = new ArrayList<Node>();

for (int i = 0; i < N; i++) {
int address = sc.nextInt();
int data = sc.nextInt();
int next = sc.nextInt();

Node n = new Node(address, data, next);
list.add(n);
}

sc.close();

ArrayList<Node> out = new ArrayList<Node>();

int end = -2;

while (end != -1) {
for (Node n : list) {
if (n.address == first) {
out.add(n);
first = n.next;
end = n.next;
}
}
}

int count = 0;

for (int i = 1; i <= N / K; i++) {
for (int j = ((i * K) - 1); j > (((i-1) * K) - 1); j--) {
System.out.println(out.get(j));
count++;
}
}
for (int i = count; i < N; i++) {
System.out.println(out.get(i));
}

// for (Node n : out) {
// System.out.println(n);
// }
}
}

运行结果

1
2
3
4
5
6
7
8
9
10
状态	分数	题目	编译器	耗时	用户	
部分正确 4 1025 Java (openjdk) 118 ms HibisciDai
测试点 结果 耗时 内存
0 答案错误 113 ms 18448 KB
1 答案错误 118 ms 18228 KB
2 答案错误 118 ms 18172 KB
3 答案正确 112 ms 17424 KB
4 答案正确 111 ms 18172 KB
5 运行超时 0 ms 0 KB
6 答案错误 114 ms 17488 KB

JAVA(openjdk)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int firstAddress = in.nextInt();
int n = in.nextInt();
int k = in.nextInt();
Node[] list = new Node[100000];
for (int i = 0; i < n; i++) {
Node temp = new Node(in.nextInt(), in.nextInt(), in.nextInt());
list[temp.address] = temp;
}
in.close();
List<Node> array = new ArrayList<>();
link(list, firstAddress, array);
reverse(array, k);
for (int i = 0; i < array.size() - 1; i++) {
System.out.printf("%05d %d %05d\n", array.get(i).address, array.get(i).data, array.get(i + 1).address);
}
int end = array.size() - 1;
System.out.printf("%05d %d -1", array.get(end).address, array.get(end).data);
}

public static void reverse(List<Node> array, int k) {
for (int i = 0; i + k <= array.size(); i += k) {
for (int m = i + k - 1, n = i; m >= n; m--, n++) {
Node temp = array.get(n);
array.set(n, array.get(m));
array.set(m, temp);
}
}
}

public static void link(Node[] list, int firstAddress, List<Node> array) {
while (firstAddress != -1) {
array.add(list[firstAddress]);
firstAddress = list[firstAddress].next;
}
}
}

class Node {
int address;
int data;
int next;

Node(int address, int data, int next) {
this.address = address;
this.data = data;
this.next = next;
}
}

运行结果

1
2
3
4
5
6
7
8
9
10
状态	分数	题目	编译器	耗时	用户
部分正确 22 1025 Java (openjdk) 121 ms HibisciDai
测试点 结果 耗时 内存
0 答案正确 112 ms 18368 KB
1 答案正确 121 ms 17440 KB
2 答案正确 114 ms 17880 KB
3 答案正确 113 ms 17896 KB
4 答案正确 108 ms 17812 KB
5 运行超时 0 ms 0 KB
6 答案正确 111 ms 16828 KB

C++

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<iostream>
const int N = 100005;
struct nodata1
{
int address;
int data;
int next;
}a[N],*b[N];
using namespace std;
int main()
{
int i, j,n,k,head,address,next,data;
scanf("%d %d %d", &head, &n, &k);
for (i = 0; i < n; i++)
{
scanf("%d %d %d", &address, &data, &next);
a[address].address = address;
a[address].data = data;
a[address].next = next;
}
j = 0;
for (i = head; i != -1; i = a[i].next)//获得a的指针
b[j++] = &a[i];
for (i = 0; i <= j-k; i += k) //翻转,<= 假设有k = j = 4,也应该翻转一次。
reverse(b + i, b + i + k);
for (i=0;i<j;i++)
{
if (i != j - 1)//由于要输出下一个元素的位置,到最后一个的时候有点特殊,所以对于b[i+1]->address,要判断一下输出。
printf("%05d %d %05d\n", b[i]->address, b[i]->data, b[i+1]->address);
else
printf("%05d %d -1\n", b[i]->address, b[i]->data);
}
return 0;
}

运行结果

1
2
3
4
5
6
7
8
9
10
状态	分数	题目	编译器	耗时	用户
答案正确 25 1025 C++ (g++) 95 ms HibisciDai
测试点 结果 耗时 内存
0 答案正确 2 ms 376 KB
1 答案正确 2 ms 380 KB
2 答案正确 2 ms 368 KB
3 答案正确 2 ms 508 KB
4 答案正确 3 ms 384 KB
5 答案正确 95 ms 4096 KB
6 答案正确 2 ms 384 KB
文章作者: HibisciDai
文章链接: http://hibiscidai.com/2019/03/01/2019-03-01-PAT乙级-1025-反转链表/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HibisciDai
支付宝打赏
微信打赏