本文共 2819 字，大约阅读时间需要 9 分钟。

题目

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^5 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, Datais 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

分析

这个题目本身是要你将链表逆序然后输出，如果认认真真的去申请空间 然后再把链表按照题目要求是很复杂的，这里注意到每个结点的地址是一个五位的整数，所以可以用算法笔记中教的静态链表来做。最关键的就是对静态链表的排序，这里怎么操作呢？和之前一样 我们在每个结点里设置bool flag变量，这个变量是为了区分开有效结点和非有效结点，另一个变量int rank来标记这个结点在整个链表的是第几个。

bool cmp1(NODE a,NODE b){
   	if( a.flag == false || b.flag == false ){
   		return a.flag > b.flag ;	}else{
   		return a.rank < b.rank ;	}}

这个cmp函数在排序时会把链表中有用的结点排在前面，没有用的排在后面，并且是按照链表结点的正序进行排列的（从结点1->2->…）

bool cmp2(NODE a,NODE b){
   	return a.rank > b.rank ;}

看似很简单，但是他的具体作用在将其排序的时候就能表现出来了：

sort(node,node+maxn,cmp1);	int i=0;	while( i < cnt ){
   		if( k==1 ) break; //k为1说明没有元素需要逆转		sort( node+i , node+i+k , cmp2 );//将每一小段的链表进行逆转		i += k;		if(i+k>cnt)break;//i+k>cnt说明要进行的逆序已经完成了不需要再排序了	}

这段代码的含义也很简单，把结点的每一小段调整循序，相当于就是对这n个结点的每一小片段中的数字进行逆转，从而实现链表的逆转，但是注意这里并不是真正将链表进行逆转了，这里只满足链表的顺序上，是符合要求的。什么意思呢？ 如果我们按照这样的代码来对结果进行输出：

for(int j=0;j

将题目的数据带入会得到什么呢？

00000 4 99999

33218 3 00000

12309 2 33218

00100 1 12309

99999 5 68237

68237 6 -1

题目需要的是：

00000 4 33218

33218 3 12309

12309 2 00100

00100 1 99999

99999 5 68237

68237 6 -1

我们差的是什么呢？就是这个结点的next的值不对！但是这个值不就是这个结点下一个结点的地址值吗？我们已经给他排好序了，那么在输出的时候只要输出第j+1个结点的地址值就完成了！将输出的代码小小改进一下：

for(int j=0;j

好了，大功告成！

#include 
   
    #include 
    
     using namespace std;const int maxn=100010;struct NODE{
   	int address,data,next;	int rank;	bool flag;}node[maxn];bool cmp1(NODE a,NODE b){
   	if(a.flag==false||b.flag==false){
   		return a.flag>b.flag;	}else{
   		return a.rank
     
      b.rank;}int main(){
   	int begin,n,k;	scanf("%d %d %d",&begin,&n,&k);	int a,b,c;	for(int i=0;i
      
       cnt)break;	}	for(int j=0;j
      
     
    
   

转载地址：https://blog.csdn.net/qq_45380840/article/details/104957428 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！