Java实现Reversing Linked List

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

addr data nextAddr

where addr is the position of the node, data is an integer, and nextAddr is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

打乱后的输入如下：

00100 10 3
00101 2 00102
00100 1 00101
00103 4 00104
00102 3 00103
00105 6 00106
00104 5 00105
00107 8 00108
00106 7 00107
00109 10 -1
00108 9 00109

Sample Output:

00102 3 00101
00101 2 00100
00100 1 00105
00105 6 00104
00104 5 00103
00103 4 00108
00108 9 00107
00107 8 00106
00106 7 00109
00109 10 -1

实现步骤：

1、读取第一行，确定链表头结点地址、链表节点数N以及节点反转的K值，然后读取所有输入行，

      将其保存为N个节点，可依次加入数组列表ArrayList中；

2、 创建节点数组nodes，最大元素个数为N+1，其中第一个元素保存头结点(指向下一个地址为 

       00100的节点)，然后在ArrayList中依次找出后续节点按顺序加入nodes中，需注意输入的N个 

       节点并不一定都在链表中，nextAddr=-1为链表尾节点标记；

3、  以K为单位反转链表所有节点，代码中已加入详细注释。

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

//反转链表
public class reverseList {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] strArr = s.split(" ");
        int startAddr = Integer.parseInt(strArr[0]);  //第一个存储数据的节点地址
        int N = Integer.parseInt(strArr[1]);          //共有N个存储数据的节点
        int K = Integer.parseInt(strArr[2]);          //每K个节点进行反转一次

        //头结点
        Node head = new Node();
        head.nextAddr = startAddr;
        Node[] nodes = new Node[N+1];
        nodes[0] = head;
        //读取所有行，返回节点数组
        ArrayList allNodes = readAllNodes(sc,N);
        //将节点按顺序存储在数组中，并去除干扰节点项,即孤立节点,数组nodes最后几个元素可能为null(用增强for遍历;也可以用迭代器遍历;也可以获取size然后用get())
        for (int i = 1; i < nodes.length; i++) {
            //如果上节点已是最后一节点，跳出循环，数组nodes后几项为null
            if(nodes[i-1].nextAddr==-1){
                N=i-1; //将N修改为链表head实际节点个数
                break;
            }
            //在数组列表中找到与上一项nextAddr相等的节点
            for(Node node : allNodes) {
                if(nodes[i-1].nextAddr == node.addr){
                       nodes[i-1].next = node;
                       nodes[i] = node;
                       break;
                }
            }
        }

        //打印当前链表的所有节点信息
//        printList(head);

        //以K个节点为单位，反转链表，链表最后几项不足K个节点无需反转
        Node result = reverseList(head,N,K);

        //打印反转链表的所有节点信息
        printList(result);
    }

    
    private static Node reverseList(Node head, int N, int K) {
        //共有几轮反转需求,此处为3
        int number = N/K;
        //剩余几个节点不需反转,此处为1
        int rest   = N%K;
        //由于单链表无法寻找前一节点，创建该临时数组指针保存一轮节点信息(第一轮结束后nodes装入[1,2,3],注意均为指针)
        Node[] nodes = new Node[K];
        //用于存储每一轮反转后的尾节点指针,链接下一轮反转后的首节点1->6,4->9,7->10
        Node linkNode = head;
        //返回的头结点
        Node result = head;
        //临时节点，用于遍历原链表的每一个节点
        Node temp   = head.next;

        //number轮反转
        //result->3->2->1;6->5->4;9->8->7;10
        for(int i=0;i6),并且记录当前轮次的尾节点，例如第二轮后linkNode指向节点4
                linkNode.nextAddr = nodes[K-1].addr;
                linkNode.next = nodes[K-1];
                linkNode = nodes[0];
            }
            //让每一轮内部逆转，第一轮后3号节点指向2,2号节点指向1,1节点指向第二轮的尾节点(即6的位置)
            for(int s=K-1; s>0; s--){
                nodes[s].nextAddr = nodes[s-1].addr;
                nodes[s].next = nodes[s-1];
            }

        }

        //如果正好全反转(例如:head->1->2->3->4->5->6->7->8->9,N=9,K=3),结束后linkNode指向7的位置,需要将其next置为null
        if(rest==0){
            linkNode.nextAddr = -1;
            linkNode.next = null;
        }else{
            //结束后temp指向10号节点的位置
            linkNode.nextAddr = temp.addr;
            linkNode.next = temp;
        }

        return result;
    }


    //读取N个节点信息
    private static ArrayList readAllNodes(Scanner sc,int N) {
            ArrayList allNodes = new ArrayList<>();
            for(int i=0;i