【欢迎关注微信公众号：计算机黑科学大全，在对话框回复：PAT乙级真题】获取全部真题详解及代码示例

反转链表

题目描述：

给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤$10^5$)、以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。

接下来有 N 行，每行格式为：

Address Data Next

其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。

输出格式：

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

输入样例：

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

输出样例：

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

题目来源：PAT乙级1025 作者：CHEN, Yue 单位：浙江大学

问题解决：

解题思想

本题要处理的细节较多。首先，单链表可采用静态链表的存储结构（当然也可以选择用指针的链式结构），定义一个结构体数组，下标为当前结点地址，两个成员分别是结点数据和下一个结点的地址；然后，需要统计输入的有效结点个数cou_n，cou_n / k即为需要反转的组数（也为调用反转函数的次数）； 以下几点容易忽略：

统计输入的有效结点个数。若用n / k来表示需要反转的次数，则导致PATOJ的最后一个测试点不通过。输出格式的控制。除了最后的-1外，其它地址都是5位非负整数，不足5位的左侧要补0。反转时第一组结点需要特殊处理。第一组结点反转后的第一个结点即为整个链表的第一个结点，需要记录下来，以便输出。头插法反转防断链处理。采用头插法反转链表，需要设置一个指针指向待处理结点的下一个结点，否则会因断链而无法到达下一个结点。

知识拓展

我们知道在C语言中，要想通过函数来改变变量的值，只通过值传递参数的形式是不能实现的，我们要通过地址传递的方式，比如数组，指针。而在C++中，我们有更为简便的方式——引用，引用相当于给对象取一个别名，通过该别名，我们可以对该对象进行相关操作，并可对主调函数的相应实参进行修改，使用时，在形参名前面加一个&符号即可(例如本题的函数形参中的addre_start，它与实参addre_start[0]对应，改变addre_start的值相应的addre_start[0]的值也会改变)。关于引用的更多讲解，大家可暂时查看C++相关书籍等。

代码示例（C/C++）

小提示：请将以下代码保存为.cpp格式（C++程序）左右滑动代码可查看全部内容

#include <cstdio> #define MAXN 100000 using namespace std; void Reverse_K(struct node Link_node[],int &addre_start,int k); //单链表结点 struct node { int data;//结点数据 int next;//下一个结点地址 }Link_node[MAXN];//下标为当前结点地址 int main() { int addre,n,k;//addre为第 1 个结点的地址 scanf("%d%d%d",&addre,&n,&k);//第一行输入 int address;//暂存输入的地址 for(int i = 0; i < n; i++){ scanf("%d",&address);//当前结点地址 //当前结点数据及下一个结点地址 scanf("%d%d",&Link_node[address].data,&Link_node[address].next); } int addre_start[2],addre_end; addre_start[0] = addre; int cou_n = 0;//统计有效的结点个数 while(addre != -1){ cou_n++; addre = Link_node[addre].next; } int flag = 1;//标记第一次反转后的第一个结点(即为整个单链表的第一个结点) for (int i = 0; i < cou_n / k; i++){//需要进行n / k次的反转 if(flag){//第一组k个结点特殊处理 addre_end = addre_start[0]; Reverse_K(Link_node,addre_start[0],k); addre = addre_start[0]; flag = 0; } else{ addre_start[0] = Link_node[addre_end].next; addre_start[1] = addre_start[0];//暂存当前待处理k个结点的第一个结点，反转后其将变为最后一个结点 Reverse_K(Link_node,addre_start[0],k); Link_node[addre_end].next = addre_start[0]; addre_end = addre_start[1]; } } while(addre != -1){//注意输出格式控制 if(Link_node[addre].next != -1){ printf("d %d d\n",addre,Link_node[addre].data,Link_node[addre].next); } else{ printf("d %d %d\n",addre,Link_node[addre].data,Link_node[addre].next); } addre = Link_node[addre].next; } return 0; } //头插法实现链表反转，通过C++的引用&来返回值，addre_start传入为 //当前待处理的一组k个结点中的第一个结点，返回为反转后的第一个结点 void Reverse_K(struct node Link_node[],int &addre_start,int k)//注意是Link_node[]，而非Link_node { int addre_s = addre_start;//暂存反转前的第一个结点地址 int p = Link_node[addre_start].next;//p指向下一个结点，防止断链 int q;//q指向当前待处理结点 for(int i = 1;i < k; i++){//k个结点要进行k-1次链的反指向 q = p; p = Link_node[p].next;//p指向下一个结点，防止断链 Link_node[q].next = addre_start;//反转 addre_start = q;//当前的第一个结点的地址 } Link_node[addre_s].next = p;//反转后第一个结点变成最后一个结点，让其指向下一组待反转的首结点 }