1025 反轉連結清單（JAVA）

給定一個常數 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      

代碼實作：

import java.io.*;
import java.util.ArrayList;

/**
 * @author yx
 * @date 2022-07-15 13:16
 */
public class Main {
    static PrintWriter out=new PrintWriter(System.out);
    static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in=new StreamTokenizer(ins);

    static class Node{
        int Address;
        int Data;
        int Next;
        Node(int Address,int Data,int Next){
            this.Address=Address;
            this.Data=Data;
            this.Next=Next;
        }
    }

    public static void main(String[] args) throws IOException {
        in.nextToken();
        int initAddress=(int) in.nval;
        in.nextToken();
        int N=(int) in.nval;//輸入的數字組數
        in.nextToken();
        int K=(int) in.nval;//需要反轉的節點個數
        ArrayList<Node> list=new ArrayList<>();//定義一個新連結清單
        Node[] nums=new Node[100000];
        for (int i = 0; i < N; i++) {
            in.nextToken();
            int address=(int) in.nval;
            in.nextToken();
            int data=(int) in.nval;
            in.nextToken();
            int next=(int) in.nval;
            nums[address]=new Node(address,data,next);
        }
        //生成一個原始連結清單
        while (initAddress!=-1){
            list.add(nums[initAddress]);
            initAddress=nums[initAddress].Next;
        }

        /*
        開始連結清單反轉
         */
//        set() 方法用于替換動态數組中指定索引的元素。
//        文法
//        set() 方法的文法為：
//        arraylist.set(int index, E element)
//        注：arraylist 是 ArrayList 類的一個對象。
//        參數說明：
//        index – 索引位置
//        element – 将在 index 位置替換進去的新元素
//                傳回值
//        傳回之前在 index 位置的元素 。
//        原文連結：https://blog.csdn.net/weixin_32770687/article/details/114511359

        /*
        這個地方一定要注意不能用N代替list.size()，這個點很關鍵，因為N代表的是輸入
        但實際上是輸入進去的資料不一定都是有用的，當無效輸入時是不會加傳入連結表的
        （輸⼊樣例中有不在連結清單中的結點的情況）
        一開始下面全部用N，會導緻最後一個測試點非零傳回
        把N改成list.size()，最後一個測試點通過
         */
        for (int i = 0; i+K-1 < list.size(); i+=K) {
            int t=i+K-1;
            //雙指針移動，往中間夾
            for (int j = i; j <t ; j++,t--) {
                Node temp=list.get(t);
                list.set(t,list.get(j));//把t位置的值用list.get(j)來替換
                list.set(j,temp);//把j位置的值用temp來替換
            }
        }
        /**
         * 這個地方有一個BUG可以鑽，就是不需要重新改變Next的值，因為每一個節點的Next就是下一個節點的Addreaa
         * 是以Next=list.get(i+1).Address，即可，最後一個的Next預設就是-1
         */
        for (int i = 0; i < list.size()-1; i++) {
            out.printf("%05d %d %05d\n",list.get(i).Address,list.get(i).Data,list.get(i+1).Address);
        }
        out.printf("%05d %d -1\n",list.get(list.size()-1).Address,list.get(list.size()-1).Data);
        out.flush();
    }
}