原题：
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
where Address is the position of the node, Data is an integer, and Next 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 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218
Sample Output:
00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1
分析：
初看是一道很简单的题目，对链表进行有规律的反转。我采取的方案如下：
1.读取输入，然后链表按其地址存放到map中（当然有猥琐的人可以存放到数组里用空间换时间）；
2.按照链表的头指针顺着下去读取链表。建一个栈，当没有达到K个时，每个读取到的值压入栈里，然后集齐K个的时候输出。技巧是一行输出的东西可以分拆分成两块，即除第一行与最后一行特殊外，其他每两行都是:
[上一地址 ] [上个值 ] [当前地址]
[当前地址] [当前值] [下一地址]
也就是说得到当前节点后，只需要补齐上一行的”当前地址”和当前行前两项即可，等到下一个节点读入时再补上这一行的最后一个“下一地址”。
3.最后，末尾别忘了NULL指针“-1”
上面的算法复杂度是O(N)
但是请务必考虑下面几个特殊情况：
1. K=1, K=N
2. 给的头指针不是整条链的头指针，而是中间某个节点的。这个问题是最后一个测试点测试的东西。我一开始也试了好多无果，还好搜到了这篇文章末尾的评论部分才得到启发！另外测试点6不会考虑给的测试例有多个next指针式NULL指针（-1）的情况，有些博客中这种说法是错误的。
例如：
00000 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218
这时候的正确输出是：
00000 4 99999 99999 5 68237 68237 6 -1
代码
#include <iostream>
#include <map>
#include <stack>
#include <string.h>
using namespace std;
struct Node
{
char fake_addr[6];
char fake_next[6];
int data;
};
int main()
{
char pStart[6];
int N, K;
cin >> pStart >> N >> K;
map<int, Node> mapNodes;
int multiEnd = 0;
for (int i = 0; i < N; i++)
{
//Read from input
char addr[6], next[6];
int data;
cin >> addr >> data >> next;
if (strcmp(next, "-1") == 0)
multiEnd++;
Node node;
node.data = data;
strcpy(node.fake_addr, addr);
strcpy(node.fake_next, next);
int key = atoi(addr);
mapNodes[key] = node;
}
if (true)
{
//奇怪的的情况，需要扫链了
int count = 0;
int nextPtr = atoi(pStart);
while (nextPtr != -1)
{
nextPtr = atoi(mapNodes[nextPtr].fake_next);
count++;
}
N = count;
}
stack<Node> workingStack;
const int LIMIT = N - N % K;
int currentFakePtr = atoi(pStart);
bool firstLine = true;
//能整除的范围
for (int i = 0; i < LIMIT; i++)
{
if (true)
{
//将node压入栈准备输出
if (currentFakePtr == -1)
{
break;
}
Node currentNode = mapNodes[currentFakePtr];
workingStack.push(currentNode);
currentFakePtr = atoi(currentNode.fake_next);
}
if (i%K == K-1)
{
//逐条弹栈并输出 (除最后一个节点的next地址)
while (!workingStack.empty())
{
Node currentNode = workingStack.top();
if (!firstLine)
cout << currentNode.fake_addr << endl; //上一行的末尾
cout << currentNode.fake_addr << " " << currentNode.data << " "; //本行的前两个元素
workingStack.pop();
firstLine = false;
}
}
}
//不能整除的范围，按顺序输出
//需要考虑一开始就不能整除的情况 (LIMIT = 0)
for (int i = LIMIT; i < N; i++)
{
if (currentFakePtr == -1)
{
break;
}
Node currentNode = mapNodes[currentFakePtr];
if (!firstLine)
cout << currentNode.fake_addr << endl; //上一行的末尾
cout << currentNode.fake_addr << " " << currentNode.data << " "; //本行的前两个元素
currentFakePtr = atoi(currentNode.fake_next);
firstLine = false;
}
cout << "-1";
return 0;
}
测试点
（这个结果还有优化的空间，不过既然已经<400ms了我就不管啦~）
| 测试点 | 结果 | 用时(ms) | 内存(kB) | 得分/满分 |
|---|---|---|---|---|
| 0 | 答案正确 | 1 | 360 | 12/12 |
| 1 | 答案正确 | 1 | 232 | 3/3 |
| 2 | 答案正确 | 1 | 360 | 2/2 |
| 3 | 答案正确 | 1 | 232 | 2/2 |
| 4 | 答案正确 | 1 | 232 | 2/2 |
| 5 | 答案正确 | 326 | 8424 | 3/3 |
| 6 | 答案正确 | 1 | 360 | 1/1 |