PAT A1074 Reversing Linked List (25分)

题意:

给N个链表结点，以及K，对每K个长度的链表做逆置，输出逆置后的链表。

题解:

不是很熟悉vector.reverse(),所以每次翻转单独处理，但是要注意最后一个结点指的地址可能会在下轮翻转中变化，所以需要进行记录。
注意%05d的输出格式会使得-1的输出出现问题，因此要分开考虑
还有一种思路是利用map做地址与存储的映射，由于10^5的int map基本上不会超时

#include <cstdio>
using namespace std;
const int N = 100010;
struct Node{
    int v;
    int next;
}node[N];

int main(){
    int start,n,k;
    scanf("%d %d %d",&start,&n,&k);
    int add;
    for(int i = 0;i<n;i++){
        scanf("%d" ,&add);
        scanf("%d %d",&node[add].v,&node[add].next);
    }
    int temp = start;
    int address[k];//存放即将反转的链表的地址
    bool flag = true;
    int time = 0;
    int lastend;
    while(temp!=-1){
        if(time!=0) lastend = address[0];
        for(int i = 0;i<k;i++){
            address[i] = temp;
            if(temp == -1){
                flag = false;
                break;
            }
            temp = node[temp].next;            
        }
        if(flag==true){//未到底开始反转
            for(int i = 0;i  < k ; i++){
                if(i==0){ 
                    node[address[0]].next = temp;                  
                }else{
                    node[address[i]].next  = address[i-1];
                }
            }
            time++;
        }else{
            break;
        }
        
        //更新start
        if(time==1){//第一次反转
            start = address[k-1];
        }else{
            node[lastend].next = address[k - 1];
        }
    }
    while(start!=-1){
        if(node[start].next!=-1) printf("%05d %d %05d\n",start,node[start].v,node[start].next);
        else printf("%05d %d %d\n",start,node[start].v,node[start].next);
        start = node[start].next;
    }
    
}

PAT A1074 Reversing Linked List (25分)

原文：https://www.cnblogs.com/shuibeng/p/13595528.html