PAT-basic-1025 反转链表 java c++

一、题目

给定一个常数 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

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

二、解析

这题可以偷懒，倒序后先改变在数组中的位置，不用更新每一个节点的next值就能正常输出了。有坑，不一定所有节点都有效。第五个测试点不用水桶法会超时。第六个测试点需要考虑并不是所有节点都有效。用正常的思维来说，先用一个list来存储所有节点，然后二重循环遍历这个list，把乱序的整成连续的，并用另外一个list存起来。但是这样第五个测试点是超时的。

三、代码

java 超时版：

查看代码

 package org.example.shuati;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

public class PAT_basic_1025 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] str = br.readLine().split("\\s+");

        String start = str[0];

        int n = Integer.parseInt(str[1]);

        int k = Integer.parseInt(str[2]);

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

        Node root = new Node();

        for (int i = 0; i < n; i++) {

            String[] s = br.readLine().split("\\s+");

            Node newNode = new Node(s[0], Integer.parseInt(s[1]), s[2]);

            if(s[0].equals(start))

                root = newNode;

            list.add(newNode);

        }

        Node[] lList = new Node[n];

        lList[0] = root;

        Node cur = root;

        int effectiveNode = 1;

        for (int i = 1; i < n; i++) {

            for (Node node : list) {

                if(node.address.equals(cur.next)){

                    lList[i] = node;

                    cur = node;

                    effectiveNode++;

                    break;

                }

            }

        }

        for(int i=0; i<effectiveNode; i+=k){

            if(i+k > effectiveNode) break;

            for(int j=i,p=i+k-1; j<p; j++,p--){

                Node temp = lList[j];

                lList[j] = lList[p];

                lList[p] = temp;

            }

        }

        for(int i=0; i<effectiveNode; i++){

            if(i+1 < effectiveNode)

                System.out.printf("%s %d %s\n", lList[i].address, lList[i].data, lList[i+1].address);

            else

                System.out.printf("%s %d -1", lList[i].address, lList[i].data);

        }

    }

    static class Node{

        private String address;

        private int data;

        private String next;

        public Node() {

        }

        public Node(String address, int data, String next) {

            this.address = address;

            this.data = data;

            this.next = next;

        }

        public String getAddress() {

            return address;

        }

        public void setAddress(String address) {

            this.address = address;

        }

        public int getData() {

            return data;

        }

        public void setData(int data) {

            this.data = data;

        }

        public String getNext() {

            return next;

        }

        public void setNext(String next) {

            this.next = next;

        }

    }

}

c++超时版，用c++改写上面的java版本仍然是超时的，将无序的输入连成一个有序的链表的二重循环花了太多时间：

查看代码

 //

// Created by yaodong on 2023/2/18.

//

#include <vector>

#include "iostream"

using namespace std;

class Node{

public:

    int address,data,next;

    Node(int address, int data, int next) : address(address), data(data), next(next) {}

    Node() {}

};

int main(){

    int initAddress, n, k;

    cin>>initAddress>>n>>k;

    vector<Node> vec;

    Node lList[n];

    Node root;

    int add,data,next;

    for(int i=0; i<n; i++){

        cin>>add>>data>>next;

        Node newNode = Node(add, data, next);

        if(add == initAddress)

            root = newNode;

        vec.push_back(newNode);

    }

    lList[0] = root;

    Node cur = root;

    //有效节点，不一定所有的输入都有效

    int eNode = 1;

    for (int i = 1; i < n; ++i) {

        for (auto item: vec){

            if(item.address == cur.next){

                lList[i] = item;

                cur = item;

                eNode++;

                break;

            }

        }

    }

    for(int i=0; i<eNode; i+=k){

        if(i+k > eNode) break;

        for(int j=i,p=i+k-1; j<p; j++,p--){

            Node temp = lList[j];

            lList[j] = lList[p];

            lList[p] = temp;

        }

    }

    for(int i=0; i<eNode; i++){

        if(i+1 < eNode)

            printf("%05d %d %05d\n", lList[i].address, lList[i].data, lList[i+1].address);

        else

            printf("%05d %d -1", lList[i].address, lList[i].data);

    }

    return 0;

}

c++ AC版，用水桶法，仔细想想，水桶法也是合理的，因为实际生活中，地址位数肯定是一样的，但是题目没有说明，每一个测试用例都是5位。或许其实连这个也应该想到的。至少猜一下。

//

// Created by yaodong on 2023/2/18.

//

#include "iostream"

using namespace std;

int main(){

    int initAddress, n, k;

    cin>>initAddress>>n>>k;

    int list[100001], data[100001], next[100001];

    int index;

    for(int i=0; i<n; i++){

        cin>>index;

        cin>>data[index]>>next[index];

    }

    //不一定所有节点都有效

    int eNode = 0;

    int nextAdd = initAddress;

    while(nextAdd != -1){

        list[eNode++] = nextAdd;

        nextAdd = next[nextAdd];

    }

    for(int i=0; i<eNode; i+=k){

        if(i+k > eNode) break;

        for(int j=i,p=i+k-1; j<p; j++,p--){

            int temp = list[j];

            list[j] = list[p];

            list[p] = temp;

        }

    }

    for(int i=0; i<eNode; i++){

        if(i+1 < eNode)

            printf("%05d %d %05d\n", list[i], data[list[i]], list[i+1]);

        else

            printf("%05d %d -1", list[i], data[list[i]]);

    }

}

巴特西

PAT-basic-1025 反转链表 java c++

输入格式：

输出格式：

输入样例：

输出样例：

最新文章

热门文章