# PTA 5-2 Reversing Linked List (25) [法一] - 线性表 - 链表反转 (PAT 1074)

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:

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         //第一行：链表的首地址add，结点个数n，每隔k个进行一次反转
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. 有其他链表干扰（即有多个-1出现）：找链表有效长度

2. k=1 或者 k=n ：不变 或者 全部逆序

3. 需逆序的起点大于有效长度 : 直接输出原链表

推荐测试：

`1. k=1或者k=n：`

00100 6 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

`2. 有其他链表干扰（即有多个-1出现）：`

00100 6 2
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 -1
99999 5 68237
12309 2 33218

– 定义结构

```struct Node {
int iData;
int iNext;
};
const int iMaxLen = 100004;
int N, K;
Node NodeList[iMaxLen];```
##### – paixu()：

1. 找有效长度：判断next是否遇到-1
2. 若需逆序的起点 > 有效长度（k > iEffectiveLength）：doPrint(iHead)
3. 更新结点总数 N 为有效长度 iEffectiveLength

K>1:
4. 初始化新链表(反转后)的首尾地址

```// iNewHead，iLastTail 表示新链表(反转后)的首尾地址
iLastTail = iTheTail;```

5. 计算反转次数：

`iReserveCount = N/K – 1`

6. 每K个翻转一次

```for(int i = 0; i < iReverseCount; ++i) {
iLastTail = iTheTail;
}```

K<=1:

`iNewHead = iHead;`

7.输出链表：

`doPrint(iNewHead);`
##### – reverseK()：

```int reverseK(int iStartHead, int iK, int *pHead, int *pTail)
//node1,node2，nodeTmp：可看作反转所需的三个指针
```
##### 完整代码：
```#include <cstdio>
struct Node {
int iData;
int iNext;
};
const int iMaxLen = 100004;
int N, K;
Node NodeList[iMaxLen];

{
break;
}
}
}
{
//!只有一个节点
if(-1 == iStartHead || iK <= 1)
return -1;
if(2 == iK){
NodeList[node1].iNext = NodeList[node2].iNext;
NodeList[node2].iNext = node1;
*pTail = node1;
return 0;
}
int nodeTmp = -1;
for(int i = 0; i < iK - 1; ++i){
nodeTmp = NodeList[node2].iNext;
NodeList[node2].iNext = node1;
node1 = node2;
node2 = nodeTmp;
}
NodeList[*pTail].iNext = node2;
return 0;
}
void paixu() {
//!找有效结点的长度：即判断next是否遇到-1
int iEffectiveLength = 1;
while(-1 != NodeList[iNodeTmp].iNext) {
++iEffectiveLength;
iNodeTmp = NodeList[iNodeTmp].iNext;
}
//!需逆序的起点大于有效长度
if(K > iEffectiveLength){
//!直接输出当前没有逆序的结点
}
//!有效长度覆盖输入的结点总个数
N = iEffectiveLength;

if(K > 1) {
int iLastTail;
//!first init reverse to decide the new head
iLastTail = iTheTail;

int iReverseCount = N / K - 1;  //!反转次数
for(int i = 0; i < iReverseCount; ++i) {
iLastTail = iTheTail;
}
}
else
}
int main() {
//!初始化 data和next都初始化为0
for(int i = 0; i < iMaxLen; ++i) {
NodeList[i].iData = 0;
NodeList[i].iNext = -1;
}
//!输入首地址，结点总数，需逆序到的数
scanf("%d %d %d", &iHead, &N, &K);