02-线性结构3 Reversing Linked List (25分)
发布日期:2022-02-10 08:11:13 浏览次数:6 分类:技术文章

本文共 3966 字,大约阅读时间需要 13 分钟。

题目

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来标记这个结点在整个链表的是第几个。
这里我的想法是写两个cmp函数来对整个链表进行排序:
第一个:

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->…)
关键是第二个cmp函数:

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

看似很简单,但是他的具体作用在将其排序的时候就能表现出来了:
给出在进行了第一次cmp1(有用的结点已经在前面被排好序了)后的排序代码:

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
   
    if(j!=cnt-1){
   
    
printf("%05d %d %05d\n",node[j].address,node[j].data,node[j].next);
}else{    
printf("%05d %d -1\n",node[j].address,node[j].data);
}
}

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

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
   
    if(j!=cnt-1){
   
    
printf("%05d %d %05d\n",node[j].address,node[j].data,node[j+1].address);
}else{    
printf("%05d %d -1\n",node[j].address,node[j].data);
}
}

好了,大功告成!
看一看整体的代码:

#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
}}bool cmp2(NODE a,NODE b){    
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 scanf("%d %d %d",&a,&b,&c);
node[a].address=a;
node[a].data=b;
node[a].next=c;
node[a].flag=false;
node[a].rank=maxn;
}
int p;
int cnt=0;
for(p=begin;p!=-1;p=node[p].next){    
node[p].flag=true;
node[p].rank= ++cnt;
}
sort(node,node+maxn,cmp1);
int i=0;
while(i if(k==1) break;
sort(node+i,node+i+k,cmp2);
i+=k;
if(i+k>cnt)break;
}
for(int j=0;j if(j!=cnt-1){    
printf("%05d %d %05d\n",node[j].address,node[j].data,node[j+1].address);
}else{    
printf("%05d %d -1\n",node[j].address,node[j].data);
}
}
return 0;}

在这里插入图片描述
这个做法占用了很多空间,也不是最快的 0.0 继续加油吧

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

上一篇:自测-4 Have Fun with Numbers (20 分)
下一篇:02-线性结构1 两个有序链表序列的合并 (15 分)

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.191.171.23]2022年08月16日 04时21分03秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章