Author: CHEN, Yue
Organization: 浙江大学
Time Limit: 400 ms
Memory Limit: 64 MB
Code Size Limit: 16 KB
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 (≤ 10^5) 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
题目意思
将链表分为 K 组，然后对其中的每一组（每组必须有 K 个元素）进行反转，对于最后一组若不满 K 个节点，则不进行反转操作。
题目分析
从算法笔记上看到的方案比较繁琐，笔者通过递归的方法来进行链表的反转。同时，在这里采用静态链表形式来存储链表。
最重要的代码是在 reverse() 部分，其中的逻辑很简单：
- 找到第 k 个节点的后面的那个元素，因为那个元素是新的递归的 head 节点；
int kNext = head;
for(int i = 0; i < k; i++) {
kNext = lists[kNext].next;
if(kNext == -1 && i < k - 1) {
return head;
}
}
如果该组节点的个数小于 k 个，那么就直接返回当前组的头节点，且不进行反转操作。
- 从 head 开始进行反转，直到当前节点的 next 节点是第 k 个节点，这个时候第 k 个节点就是这一组节点中的头节点，而 head 节点反而是这组节点的尾节点；
链表反转的主要代码如下：
int current = head;
int prev = kNext;
while(current != kNext) {
int next = lists[current].next;
lists[current].next = prev;
prev = current;
current = next;
}
- 如何将一个分组（非最后一个分组）的尾节点和下一个分组的头节点进行关联是一个关键点，否则将造成最后反转的结果是紊乱的。于是我们考虑将reverser() 的返回值设置为本组节点反转之后的头节点，那么在递归调用 reverse() 之后呢需要将本组节点反转之后的尾节点和递归调用的结果（上一组节点反转之后的头节点）进行关联。
lists[head].next= reverse(kNext, k)
注意：关联操作一定要在递归调用 reverse() 之后进行，因为每组节点进行反转之后的结果都是变化的，如果不及时更改上一组的尾节点所指向的下一个节点，将会造成错误。
题目解答
https://github.com/JohnNiang/algorithm/blob/master/A1074/main.cpp
#include <iostream>
#include <algorithm>
using namespace std;
// A1074: Reversing Linked List
// <https://pintia.cn/problem-sets/994805342720868352/problems/994805394512134144>
const int MAX = 100000;
struct LinkedList {
int data;
int next;
int address;
} lists[MAX];
void print(LinkedList& list) {
printf("%05d %d", list.address, list.data);
if(list.next != -1) {
printf(" %05d", list.next);
} else {
printf(" %d", list.next);
}
printf("\n");
}
void print(int head) {
int current = head;
while(current != -1) {
LinkedList list = lists[current];
print(list);
current = list.next;
}
}
int reverse(int head, int k) {
if(head == -1) {
return head;
}
int kNext = head;
for(int i = 0; i < k; i++) {
kNext = lists[kNext].next;
if(kNext == -1 && i < k - 1) {
return head;
}
}
int current = head;
int prev = kNext;
while(current != kNext) {
int next = lists[current].next;
lists[current].next = prev;
prev = current;
current = next;
}
lists[head].next= reverse(kNext, k);
return prev;
}
int main() {
int head = 0;
int N = 0;
int K = 0;
cin >> head >> N >> K;
for(int i = 0; i < N; i++) {
int address = 0;
cin >> address;
cin >> lists[address].data >> lists[address].next;
lists[address].address = address;
}
head = reverse(head, K);
print(head);
return 0;
}