# PAT 解题报告 1074. Reversing Linked List (25)

### 1074. 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.

### 1074. Reversing Linked List 算法分析：

```#include <cstdio>

struct Node {
int iData;
int iNext;
};

const int iMaxLen = 100004;

int N, K;
Node NodeList[iMaxLen];

printf("%.5d %d -1\n",
break;
}
printf("%.5d %d %.5d\n",
}
}

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 gao() {
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() {
for(int i = 0; i < iMaxLen; ++i) {
NodeList[i].iData = 0;
NodeList[i].iNext = -1;
}
scanf("%d %d %d", &iHead, &N, &K);
for(int i = 0; i < N; ++i) {
scanf("%d %d %d", &iSingleNodeAddress, &iSingleNodeData, &iSingleNodeNext);
}
gao();
return 0;
}
```

### 1074. Reversing Linked List 注意点：

(1) 这次PAT最坑的一个题目吧, 输入可能不止一个链表, 有些节点不在要反转的那个链表上, 输出的时候应当忽略. 比如

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

(2) 另外注意指针的使用, 还有特例K = 1, K = N之类的情况, 因为上面的特殊坑点, 有可能是打断了的多个链表, 我们的K也有可能大于有效节点数.

Written on March 6, 2014