PAT甲级1074.

目录

A1074

题目

样例

输入:

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

思路和坑点

　　有两种思路。
　　第一种：将链表存放在数组中，然后每K个逆置，结尾不足k个不逆置。
　　第二种：没k个进行一组链表的头插，实现逆置。
　　坑点:
　　如果使用数组的方法，需要过滤掉不属于链表中的多余结点。

AC代码（数组实现）

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef struct node{                    //结点结构体 
    int id,data,next;
}Node;
vector<Node> all(MAXN);                 //存放所有输入结点 
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int head,n,k;
    scanf("%d%d%d",&head,&n,&k);    
    for(int i=0;i<n;i++){               //读取输入 
        int id;
        scanf("%d",&id);
        all[id].id=id;
        scanf("%d%d",&all[id].data,&all[id].next);
    }
    vector<Node> List;                  //用数组存放有效结点 
    for(int i=head;i!=-1;i=all[i].next)
        List.push_back(all[i]);         //有效结点存入数组 
    for(int i=0;i<List.size()/k;i++)//每K个逆序 
        reverse(List.begin()+i*k,List.begin()+(i+1)*k);
    int i;
    for(i=0;i<List.size()-1;i++)        //输出 ，每一个的next是下一个的id，最后一个特殊处理 
        printf("%05d %d %05d\n",List[i].id,List[i].data,List[i+1].id);
    printf("%05d %d -1",List[i].id,List[i].data);
    return 0;
} 

AC代码（链表实现）

#include<bits/stdc++.h>
using namespace std;
typedef struct{
    int id,data,next;
}Node;
Node List[100005]; 
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n,k;                            //n为所谓的节点数量 ，k为逆转数 
    int cnt=0;                          //用于记录已经处理的节点数量 
    int L=100001;                       //链表表头的空结点 
    int head,temp,r,rear;               //head为链表第一个结点 ，temp为保证链表不掉链，r用于最后的遍历输出，rear用于记录每次链表的尾巴，每k次需要从尾巴处头插 
    cin>>head>>n>>k;
    for(int i=0;i<n;i++){               //读入数据 
        int index;
        scanf("%d",&index);
        scanf("%d%d",&List[index].data,&List[index].next);
    }
    n=0;                                //统计排除多余结点 
    for(int i=head;i!=-1;i=List[i].next){
        n++;
    }
    List[L].next=-1;                    //摘下空的头结点，开始头插 
    rear=head;                          //每次第一个头插的结点会成为链表的尾巴 
    while(cnt!=n-n%k){                  //如果不是k的整数倍个结点只需要处理前n-n%k个结点 
        temp=List[head].next;
        List[head].next=List[L].next;
        List[L].next=head;;
        cnt++;
        if(cnt%k==0){                   //每当头插k个实现了逆序后，要更新到当前链表的尾巴处继续新一轮的头插 
            L=rear;
            rear=temp;
        }
        head=temp; 
    }
    if(cnt!=n){                         //如果有尾巴，处理尾巴 
        List[L].next=head;
    }
    //输出 
    for(r=List[100001].next;List[r].next!=-1;r=List[r].next){
        printf("%05d %d %05d\n",r,List[r].data,List[r].next);
    }
    printf("%05d %d -1",r,List[r].data);
    return 0;    
}