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 个元素不反转。

辅助描述

作者: CHEN, Yue
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB

输入格式

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

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

Address Data Next

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

输出格式

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

输入样例

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

输出样例

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

算法实现

JAVA(openjdk)

代码

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);
//        }
    }
}

运行结果

状态	分数	题目	编译器	耗时	用户	
部分正确	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)

代码

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;
    }
}

运行结果

状态	分数	题目	编译器	耗时	用户
部分正确	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++

代码

#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;
}

运行结果

状态	分数	题目	编译器	耗时	用户
答案正确	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