PAT A1074 Reversing Linked List

题目链接

一定要注意读题，题目中要求一段一段的翻转！！！

栈解法

#include <cstdio>
#include <stack>

using namespace std;
const int N = 1e6 + 10;
struct Node {
    int data, next;
} node[N];


int main() {
    int head, n, k, t, ed;
    stack<int> s;
    scanf("%d%d%d", &head, &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &t);
        scanf("%d%d", &node[t].data, &node[t].next);
    }

    while (head != -1) {
        s.push(head);
        head = node[head].next;
    }
    int tp, num = 0, size = s.size(), ans,head1;
    //找到末尾开始的位置
    while (num % k != size % k) {
        tp = s.top();
        s.pop();
        head = tp;
        num++;
    }
    head1=head;
    num++;

    if (!s.empty()){
        ans=head=s.top();
        s.pop();
    }
  
    while (!s.empty()) {
        while (num % k != size % k) {
            tp = s.top();
            s.pop();
            node[head].next = tp;
            head = tp;
            num++;
        }
        node[head].next = head1;
        head1 = ans;

        if (s.empty()) break;
        else {
            head = s.top();
            s.pop();
            ans = head;
        }

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

静态链表五步法

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;
struct Node{
    int address,data,next,order;
}node[N];
bool cmp(Node& a,Node& b){
    return a.order<b.order;
}


int main(){
    //2.初始化并读入
    for(int i=0;i<N;i++){
        node[i].order=N;
    }
    int head,n,k,addr;
    scanf("%d%d%d",&head,&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&addr);
        scanf("%d%d",&node[addr].data,&node[addr].next);
        node[addr].address=addr;
    }
    //3.遍历赋值，并计数
    int p=head,cnt=0;
    while(p!=-1){
        node[p].order=cnt++;
        p=node[p].next;
    }
    //4.排序
    sort(node,node+N,cmp);
    //5.输出结果
    n=cnt;
    for(int i=0;i<n/k;i++){//遍历n/k个块
        //每个块先反向打印一波
        for(int j=(i+1)*k-1;j>i*k;j--){
            printf("%05d %d %05d\n",node[j].address,node[j].data,node[j-1].address);
        }
        //打印这一块的最后一个节点
        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);//这里要跳到下一个块的最后一个节点，所以加2
        } 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++){
                    if(i<n-1) printf("%05d %d %05d\n",node[i].address,node[i].data,node[i+1].address);
                    else printf("%05d %d -1\n",node[i].address,node[i].data);
                }
            }
        }
    }

    return 0;
}