【1074】Reversing Linked List (25 分)

下面方法感觉好麻烦。。。

感觉黎大佬的做法更简单https://blog.csdn.net/qq_33657357/article/details/80407542

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      const int maxn=100010;
     
    
   

    

     

    
    

     

      //算法de思路：结点结构体的order初始化为maxn(无效结点)，再按照静态链表结点排序(order依次赋值)
     
    
   

    

     

    
    

     

      五个步骤，key：第五个中对每一块最后一个结点的next地址的处理
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //定义静态链表(步骤1)
     
    
   

    

     

    
    

     

      struct Node{  
     
    
   

    

     

    
    

     
	int address,data,next;
     
    
   

    

     

    
    

     
	int order;  //结点在链表中的序号，无效结点记为maxn
     
    
   

    

     

    
    

     

      }node[maxn];
     
    
   

    

     

    
    

     

      bool cmp(Node a,Node b){
     
    
   

    

     

    
    

     
	return a.order<b.order; //按order从小到大排序
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
   
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
	//初始化(步骤2)
     
    
   

    

     

    
    

     
	for(int i=0;i<maxn;i++){  
     
    
   

    

     

    
    

     

      		node[i].order=maxn;  //初始化全部为无效结点
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int begin,n,K,address;
     
    
   

    

     

    
    

     
	scanf("%d%d%d",&begin,&n,&K);  //起始地址，结点个数，步长
     
    
   

    

     

    
    

     
	//初始化静态链表
     
    
   

    

     

    
    

     
	for(int i=0;i<n;i++){
     
    
   

    

     

    
    

     
		scanf("%d",&address);
     
    
   

    

     

    
    

     
		scanf("%d%d",&node[address].data,&node[address].next);
     
    
   

    

     

    
    

     

      		node[address].address=address;  //别漏了这步，“两个”address不同
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int p=begin,count=0; //count计数有效结点的数目
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	//遍历链表找出单链表的所有有效结点(步骤3)
     
    
   

    

     

    
    

     
	while(p!=-1){  
     
    
   

    

     

    
    

     

      		node[p].order=count++; //结点在单链表中的序号
     
    
   

    

     

    
    

     

      		p=node[p].next;  //下一个结点
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//按单链表从头到尾顺序排列(步骤4)
     
    
   

    

     

    
    

     
	sort(node ,node+maxn,cmp);  
     
    
   

    

     

    
    

     
	//有效结点为前count个结点，为了书写方便就把count赋值给n
     
    
   

    

     

    
    

     

      	n=count;
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	//单链表已经形成,按照题目要求输出(步骤5)
     
    
   

    

     

    
    

     
	for(int i=0;i<n/K;i++){  //枚举完整的n/K块
     
    
   

    

     

    
    

     
		for(int j=(i+1)*K-1 ; j>i*K;  j-- ){  //第i块倒着输出
     
    
   

    

     

    
    

     
			printf("%05d %d %05d\n",node[j].address, node[j].data,  node[j-1].address);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		//下面是每一块的最后一个结点的next地址的处理
     
    
   

    

     

    
    

     
		printf("%05d %d ",node[i*K].address,node[i*K].data);
     
    
   

    

     

    
    

     
		if(i<n/K-1){ //如果不是最后一块,就指向下一块的最后一个结点
     
    
   

    

     

    
    

     
			printf("%05d\n",node[ (i+2)*K-1 ].address );
     
    
   

    

     

    
    

     

      		}else{  //如果是最后一块时
     
    
   

    

     

    
    

     
			if(n%K==0) { //恰好是最后一个结点时，输出-1
     
    
   

    

     

    
    

     
				printf("-1\n");
     
    
   

    

     

    
    

     

      		}else{  //剩下不完整的块按照原先的顺序输出
     
    
   

    

     

    
    

     
			printf("%05d\n",node[ (i+1)*K ].address);//注意换行符
     
    
   

    

     

    
    

     
			for(int i=n/K*K ;  i<n ;i++){
     
    
   

    

     

    
    

     
				printf("%05d %d ",node[i].address,node[i].data);
     
    
   

    

     

    
    

     
				if(i<n-1){
     
    
   

    

     

    
    

     
					printf("%05d\n",node[i+1].address);
     
    
   

    

     

    
    

     

      				}else{
     
    
   

    

     

    
    

     
					printf("-1\n");
     
    
   

    

     

    
    

     

      				}
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}	
     
    
   

    

     

    
    

     
	system("pause");
     
    
   

    

     

    
    

     
	return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/98447827