题目来源：
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:
Address Data Next
whereAddressis the position of the node,Datais an integer, andNextis 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 6 400000 4 9999900100 1 1230968237 6 -133218 3 0000099999 5 6823712309 2 33218Sample Output:00000 4 3321833218 3 1230912309 2 0010000100 1 9999999999 5 6823768237 6 -1解法1： 有一个测试点通不过，，原因是运行超时import java.util.HashMap;import java.util.Scanner;public class Main{static class Node{int value ;String next ;public Node(int value,String next){this.value=value;this.next=next;}public int getValue() {return value;}public void setValue(int value) {this.value = value;}public String getNext() {return next;}public void setNext(String next) {this.next = next;}}/***（方法说明）*@param 无*@return 无*@throws 无*/public static void main(String[] args){Scanner scanner = new Scanner(System.in);//头节点地址String head =scanner.next();//总共的节点数int n = scanner.nextInt();//转换因子 kint k = scanner.nextInt();//存储节点HashMap<String,Node> hashMap = new HashMap<String,Node>();for(int i=0;i<n;++i){String key = scanner.next();int value = scanner.nextInt();String next = scanner.next();Node node = new Node(value,next);hashMap.put(key, node);}//存储要输出的4个addressString[] address =new String[k];//address的下标int index =0;address[index++]=head;Node node = hashMap.get(head);//下一个地址的指针String next = node.next;//第一次输出boolean firsline=false;while(!next.equals("-1")){if(index==k){for(int i=(k-1);i>=0;–i){if(i!=k-1 || firsline)System.out.println(address[i]);System.out.print(address[i]+" "+hashMap.get(address[i]).value+" ");firsline = true;}index=0;}node = hashMap.get(next);address[index++]= next;next = node.next;}if(index>0){if(index==k){for(int i=(k-1);i>=0;–i){if(i!=k-1 || firsline)System.out.println(address[i]);System.out.print(address[i]+" "+hashMap.get(address[i]).value+" ");firsline = true;}index=0;}else{for(int i=0;i<index;++i){System.out.println(address[i]);System.out.print(address[i]+" "+hashMap.get(address[i]).value+" ");}}}System.out.println("-1");}}
解法2:参考
#include <stdio.h>#include <vector>#include <algorithm>using namespace std;#define MAXN 100001typedef struct{int addr;int data;int next;}Node;Node nodes[MAXN];vector<Node> list;int main(){int firstAdd, n, k;scanf("%d%d%d", &firstAdd, &n, &k);while(n–){Node nn;scanf("%d%d%d", &nn.addr, &nn.data, &nn.next);nodes[nn.addr] = nn;}int address = firstAdd;while(address != -1){list.push_back(nodes[address]);address = nodes[address].next;}int length = list.size();int round = length/k;for(int i = 1; i <= round; ++i){int start = (i-1)*k;int end = i*k;reverse(list.begin() + start, list.begin() + end);}for(int i = 0; i < length-1; ++i){printf("%05d %d %05d\n", list[i].addr, list[i].data, list[i+1].addr);}printf("%05d %d %d\n",list[length-1].addr, list[length-1].data, -1);return 0;}
害怕攀登高峰的人，永远在山下徘徊。
