1 package ygh.study.demo1;
  2 
  3 import java.util.ArrayList;
  4 import java.util.List;
  5 import java.util.Scanner;
  6 /*
  7 Given a constant KKK and a singly linked list LLL, you are supposed to reverse the links of every KKK elements on LLL. For example, given LLL being 1→2→3→4→5→6, if K=3K = 3K=3, then you must output 3→2→1→6→5→4; if K=4K = 4K=4, you must output 4→3→2→1→5→6.
  8 Input Specification:
  9 
 10 Each input file contains one test case. For each case, the first line contains the address of the first node, a positive NNN (≤105\le 10^5≤10?5??) which is the total number of nodes, and a positive KKK (≤N\le N≤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.
 11 
 12 Then NNN lines follow, each describes a node in the format:
 13 
 14 Address Data Next
 15 
 16 where Address is the position of the node, Data is an integer, and Next is the position of the next node.
 17 Output Specification:
 18 
 19 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.
 20 Sample Input:
 21 
 22 00100 6 4
 23 00000 4 99999
 24 00100 1 12309
 25 68237 6 -1
 26 33218 3 00000
 27 99999 5 68237
 28 12309 2 33218
 29 
 30 Sample Output:
 31 
 32 00000 4 33218
 33 33218 3 12309
 34 12309 2 00100
 35 00100 1 99999
 36 99999 5 68237
 37 68237 6 -1
 38 */
 39 public class Demo1 {
 40 
 41     public static void main(String[] args) {
 42         List<Node> nodeList = new ArrayList<Node>();
 43         // nodeList.add(new Node("00000", 4, "99999"));
 44         // nodeList.add(new Node("00100", 1, "12309"));
 45         // nodeList.add(new Node("68237", 6, "-1"));
 46         // nodeList.add(new Node("33218", 3, "00000"));
 47         // nodeList.add(new Node("12309", 2, "33218"));
 48         // nodeList.add(new Node("99999", 5, "68237"));
 49         Scanner sc = new Scanner(System.in);
 50         String initAddress = sc.next();
 51         int n = sc.nextInt();
 52         int k = sc.nextInt();
 53         for (int i = 0; i < n; i++) {
 54             String address = sc.next();
 55             int element = sc.nextInt();
 56             String nextAddrss = sc.next();
 57             Node node = new Node(address, element, nextAddrss);
 58             nodeList.add(node);
 59         }
 60         sc.close();
 61         List<Node> sortedList = sort(nodeList, initAddress, n);
 62         transmit(sortedList, k);
 63         for (Node node : sortedList) {
 64             System.out.println(node.toString());
 65             System.err.println();
 66         }
 67 
 68     }
 69 
 70     public static void transmit(List<Node> list, int k) {
 71         int length = list.size();
 72         int i = 0;
 73         if (length < k) {
 74             track(list, 0, length);
 75             return;
 76         } else {
 77             while (i <= length) {
 78                 if (i + k <= length) {
 79                     track(list, i, i + k);
 80                     i = i + k;
 81                 } else {
 82                     track(list, i + k, length);
 83                     i = i + k;
 84                 }
 85             }
 86         }
 87     }
 88 
 89     public static void track(List<Node> list, int begin, int end) {
 90         int mid = (begin + end) / 2;
 91         for (int i = begin; i < mid; i++) {
 92             Node temp = list.get(i);
 93             list.set(i, list.get(end - i - 1));
 94             list.set(end - i - 1, temp);
 95         }
 96     }
 97 
 98     public static List<Node> sort(List<Node> list, String initAddress, int length) {
 99         List<Node> tempList = new ArrayList<Node>();
100         tempList.add(getNodeByAddress(list, initAddress));
101         for (int i = 1; i < length; i++) {
102             tempList.add(getNodeByAddress(list, tempList.get(i - 1).getNextAddress()));
103         }
104 
105         return tempList;
106     }
107 
108     public static Node getNodeByAddress(List<Node> list, String address) {
109         for (Node node : list) {
110             if (node.getAddress().equals(address)) {
111                 return node;
112             }
113         }
114         return null;
115     }
116 
117 }
118 
119 class Node {
120     private String address;
121 
122     private int element;
123 
124     private String nextAddress;
125 
126     public String getAddress() {
127         return address;
128     }
129 
130     public void setAddress(String address) {
131         this.address = address;
132     }
133 
134     public int getElement() {
135         return element;
136     }
137 
138     public void setElement(int element) {
139         this.element = element;
140     }
141 
142     public String getNextAddress() {
143         return nextAddress;
144     }
145 
146     public void setNextAddress(String nextAddress) {
147         this.nextAddress = nextAddress;
148     }
149 
150     public Node(String address, int element, String nextAddress) {
151         super();
152         this.address = address;
153         this.element = element;
154         this.nextAddress = nextAddress;
155     }
156 
157     public Node() {
158         super();
159     }
160 
161     @Override
162     public String toString() {
163         return this.getAddress() + " " + this.getElement() + " " + this.getNextAddress();
164     }
165 
166 }