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

题意说的很清楚了，这种题的话，做的时候最好就是在纸上自己亲手模拟一下，清楚一下各个指针的情况，

这样写的时候就很清楚各个指针变量保存的是什么值。

PS：一次AC哈哈，所以说自己动手在纸上画画还是很有好处的~

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <cmath>

#include <queue>

using namespace std;

const int maxn=+;

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=;i<n;i++){

        scanf("%d %d %d",&addr,&data,&next);

        node[addr].data=data;

        node[addr].next=next;

    }

    int p=first;

    int lastRear=-;//上K个节点的最后节点的地址

    int newfirst; //新链表的首地址

    while(p!=-){

        int head,last;

        head=last=p;

        int tmp=head;

        //用于判断剩余的节点个数是否>=k个

        for(int i=;i<k- && tmp!=-;i++){

            tmp=node[tmp].next;

        }

        //若剩余节点<k,则按原来的顺序即可

        if(tmp==-){

            ans[lastRear].next=p;

            while(p!=-){

                ans[p].data=node[p].data;

                ans[p].next=node[p].next;

                lastRear=p;

                p=node[p].next;

            }

            break;

        }

        for(int i=;i<k && p!=-;i++){

            ans[p].data=node[p].data;

            if(i!=)

                ans[p].next=last;//后一个指向前一个

            last=p;

            p=node[p].next;

        }

        if(lastRear!=-){

            ans[lastRear].next=last; //上K个节点的末尾指向当前K个节点的最后一个

        }

        else{

            newfirst=last; //新链表的首地址

        }

        lastRear=head; //反转，头部变成了末尾

    }

    ans[lastRear].next=-;

    while(newfirst!=-){

        if(ans[newfirst].next!=-)

            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 ;

}