PAT甲题题解-1074. Reversing Linked List (25)-求反向链表

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <queue>
using namespace std;
const int maxn=100000+5;

struct Node{
    int data;
    int next;
}node[maxn],ans[maxn];
int main()
{
    int first,n,k;
    int addr,data,next;
    scanf("%d %d %d",&first,&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d %d %d",&addr,&data,&next);
        node[addr].data=data;
        node[addr].next=next;
    }
    int p=first;
    int lastRear=-1;//上K个节点的最后节点的地址
    int newfirst; //新链表的首地址
    while(p!=-1){
        int head,last;
        head=last=p;
        int tmp=head;
        //用于判断剩余的节点个数是否>=k个
        for(int i=0;i<k-1 && tmp!=-1;i++){
            tmp=node[tmp].next;
        }
        //若剩余节点<k,则按原来的顺序即可
        if(tmp==-1){
            ans[lastRear].next=p;
            while(p!=-1){
                ans[p].data=node[p].data;
                ans[p].next=node[p].next;
                lastRear=p;
                p=node[p].next;
            }
            break;
        }
        
        for(int i=0;i<k && p!=-1;i++){
            ans[p].data=node[p].data;
            if(i!=0)
                ans[p].next=last;//后一个指向前一个
            last=p;
            p=node[p].next;
        }
        if(lastRear!=-1){
            ans[lastRear].next=last; //上K个节点的末尾指向当前K个节点的最后一个
        }
        else{
            newfirst=last; //新链表的首地址
        }
        lastRear=head; //反转，头部变成了末尾
    }
    ans[lastRear].next=-1;

    while(newfirst!=-1){
        if(ans[newfirst].next!=-1)
            printf("%05d %d %05d\n",newfirst,ans[newfirst].data,ans[newfirst].next);
        else
            printf("%05d %d %d\n",newfirst,ans[newfirst].data,ans[newfirst].next);
        newfirst=ans[newfirst].next;
    }
    return 0;
}